[Algorithm] 백준 2527 직사각형

[ 문제 ]

x2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다.

직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (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개의 줄에 각각 차례대로 출력해야 한다.

 

[ 예제 입력 ]

3 10 50 60 100 100 200 300

45 50 600 600 400 450 500 543

11 120 120 230 50 40 60 440

35 56 67 90 67 80 500 600

 

[ 예제 출력 ]

d

a

a

b

 

---

두 직사각형의 길이를 더한 값과 좌표상에서 직사각형이 존재하는 범위를 비교하는 방법으로 결과를 도출했습니다.

 

import java.util.*;
import java.io.*;

public class Main {
	
	public static char isRectangle (int minX, int minY, int maxX, int maxY, int width1, int height1, int width2, int height2) {
		if (((width1+width2 == maxX-minX) && (height1+height2 > maxY-minY)) || ((height1+height2 == maxY-minY) && (width1+width2 > maxX-minX)))
			return 'b';
		else if ((width1+width2 == maxX-minX) && (height1+height2 == maxY-minY)) // 점이 겹치는 경우
			return 'c';
		else if ((width1+width2 < maxX-minX) || (height1+height2 < maxY-minY)) // 공통부분이 없는 경우
			return 'd';
		else
			return 'a';
	}


	public static void main (String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int t = 0; t < 4; t++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int p1 = Integer.parseInt(st.nextToken());
			int q1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			int p2 = Integer.parseInt(st.nextToken());
			int q2 = Integer.parseInt(st.nextToken());
			
			
			int minX = Math.min(x1, x2); // 입력받은 x좌표의 최솟값
			int maxX = Math.max(p1, p2); // 입력받은 x좌표의 최댓값
			int minY = Math.min(y1, y2); // 입력받은 y좌표의 최솟값
			int maxY = Math.max(q1, q2); // 입력받은 y좌표의 최댓값
			
			int width1 = p1 - x1; // 첫번째 직사각형의 가로 길이
			int height1 = q1 - y1; // 첫번째 직사각형의 세로 길이
			int width2 = p2 - x2; // 두번째 직사각형의 가로 길이
			int height2 = q2 - y2; // 두번째 직사각형의 세로 길이
			
			System.out.println(isRectangle(minX, minY, maxX, maxY, width1, height1, width2, height2));
		}
	}
}