두 직사각형 > 문제은행

본문 바로가기


실전대비 Level4

1367 : 두 직사각형

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 9 회    시도횟수: 36 회   



평면에 N개의 점이 주어져 있을 때, 이 N개의 점을 보두 포함하는 가능한 작은 2개의 직사각형을 찾으려 한다.

 

두 개의 직사각형은 축에 평행하며, 이 두 사각형 중 넓이가 큰 사각형의 넓이를 최소화해야 한다.

 

 

e3050b66a1b29a01767400d7560a4131_1449731
 

 

단, 위 그림에서 보는 바와 같이 두 직사각형은 위와 같이 서로 겹치지 않아야 하며 (변 혹은 꼭지점 역시 접하면 안된다.) 두 사각형이 같은 모양이거나 같은 넓이를 가질 필요는 없다.

 

문제는 두 직사각형 중 큰 것의 넓이를 최소화 하여 그 넓이를 출력하는 것이다. 또한, 직사각형은 그 너비 혹은 높이가 0인 경우도 가능하며, 그런 경우 직사각형의 넓이는 0이다.


입력의 첫 줄에는 점의 개수 N(1≤N≤10,000)이 주어지며, 그 이후 N개의 줄에 N개의 점의 좌표가 두 개의 정수로 한줄에 주어진다. 좌표값은 모두 정수로 주어지며, -3,000,000 이상 3,000,000이하의 값을 가진다. 주어지는 점은 X좌표와 Y좌표가 겹치는 점은 없다고 가정한다.



입력에 대해서 문제에서 요구하는 두 개의 직사각형 중 넓이가 큰 것의 넓이를 출력한다.


[Copy]
4
1 1
2 3
3 4
5 -1
[Copy]
6




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.