[백준] 2527 - 직사각형 (자바/Java)

문제

2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다.

이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q 로 표현된다. 단 항상 x<p, y<q 이다. 예를 들어 위 그림에 제시된 직사각형이라면 아래와 같이 표현된다.

3 2 9 8

두 개의 직사각형은 그 겹치는 부분의 특성에 따라 다음 4가지 경우로 분류될 수 있다. 

먼저 두 직사각형의 겹치는 부분이 직사각형인 경우이다. 아래 그림(a)는 공통부분이 직사각형인 경우의 3가지 예를 보여준다,

그림 (a)

또는 겹치는 부분이 아래 그림 (b)와 같이 선분이 될 수도 있고, 그림 (c)와 같이 점도 될 수 있다. 

그림 (b)

그림 (c)

마지막으로 아래 그림 (d)와 같이 공통부분 없이 두 직사각형이 완전히 분리된 경우도 있다.

그림 (d)

여러분은 두 직사각형의 겹치는 부분이 직사각형인지, 선분인지, 점인지, 아니면 전혀 없는 지를 판별해서 해당되는 코드 문자를 출력해야 한다. 

공통부분의 특성코드 문자

직사각형	a
선분	b
점	c
공통부분이 없음	d

입력

4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사각형의 좌표 값은 1이상 50,000 이하의 정수로 제한된다. 

출력

4개의 각 줄에 주어진 두 직사각형의 공통부분을 조사해서 해당하는 코드 문자를 출력파일의 첫 4개의 줄에 각각 차례대로 출력해야 한다.

---

무지성으로 모든 조건을 처리하려다가 시간을 잡아먹었다.

쉽게 생각하면 겹치지 않는 것부터 조건을 하나씩 제거하면 되는데, 그 조건들을 개별로 하나하나 처리하려고 하다가 결국 구멍이 발생하였다.

이 경우는 겹치지 않는 d부터 처리하는 게 핵심이다.

 

사각형1의 좌표를 (x1, y1) (x2, y2)라고 하고, 사각형2의 좌표를 (x3, y3) (x4, y4)라고 한다.

 

• d: 겹치지 않는 경우

겹치지 않는 경우는 x2가 x3보다 작은 경우, 즉 사각형에서 가장 큰 좌표가 다른 사각형의 가장 작은 좌표보다 작은 경우이다.

			if (x2 < x3 || y2 < y3 || x4 < x1 || y4 < y1)

• c: 점

점은 좌표가 겹치는 경우인데, 중요한 것은 같은 위치에 있는 좌표가 겹치면 안된다는 점이다.

만약 왼쪽 아래의 점이라면 다른 사각형의 왼쪽 아래가 아닌 오른쪽 위의 좌표와 겹쳐야 한다.

이 사진을 통해 그 이유를 확인할 수 있다.

• b: 선분

점을 처리해준 후, 선분은 x와 y 중 한 좌표는 같지만 다른 좌표는 다른 경우다.

처음에는 여기서 선분끼리 겹치지 않는 경우를 처리하려고 했는데, 이미 d에서 제외하였으니 다른 경우만 확인하면 된다.

• a: 직사각형

그 외의 모든 경우는 직사각형으로 겹치는 경우다.

 

package BOJ0811;

import java.util.Scanner;

public class BOJ_2527_직사각형 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arrX = new int[4];
		int[] arrY = new int[4];
		String result = "";
		for (int i = 0; i < 4; i++) {
			result = "d";
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();
			int x2 = sc.nextInt();
			int y2 = sc.nextInt();

			int x3 = sc.nextInt();
			int y3 = sc.nextInt();
			int x4 = sc.nextInt();
			int y4 = sc.nextInt();

			// d부터 체크
			if (x2 < x3 || y2 < y3 || x4 < x1 || y4 < y1)
				result = "d";
			else if ((x1 == x4 && y1 == y4) || (x1 == x4 && y2 == y3) || (x2 == x3 && y2 == y3)
					|| (x2 == x3 && y1 == y4))
				result = "c";
			else if (x1 == x4 || x2 == x3 || y1 == y4 || y2 == y3)
				result = "b";
			else {
				result = "a";
			}

			System.out.println(result);
		}
	}
}