최소 포함 사각형 > 문제은행



문제은행

1482 : 최소 포함 사각형

제한시간: 1000 ms    메모리제한: 0 MB
해결횟수: 5 회    시도횟수: 7 회   



2차원 좌표 평면 내에 짝수개의 점이 주어져 있다. 임의의 정수 좌표의 한 곳을 잡고 좌표축에 평행한 임의의 사각형을 만들었을 때, 사각형 내에 주어진 점이 전체 점의 개수의 절반 이상 포함되는 사각형 중 최소의 넓이를 가지는 사각형을 찾고자 한다. 여기서 점이 사각형 내에 포함 된다는 것은, 만들어진 사각형 영역 내에 위치한다는 것이고, 만들어진 사각형의 변 혹은 꼭지점에 겹치는 점 역시 사각형에 포함되지 않는 것으로 . 점의 개수와 점의 좌표들의 위치가 주어졌을 때, 이러한 조건을 만족하는 사각형의 최소 넓이를 찾는 프로그램을 작성하라.

예를 들어 (100,100), (200,200)의 좌표를 가진 2개의 점이 주어졌을 때, (99,99), (101,101)가 꼭지점을 이루는 사각형이나, (199,199), (201,201)가 꼭지점을 이루는 사각형을 잡을 경우 위의 조건을 만족하게 되고 이 경우 최소 넓이는 4가 된다.




첫 번째 줄에는 점의 개수를 뜻하는 짝수인 정수 N(N≤100)개가 주어지며, 그 다음 줄부터 N개의 점의 좌표가 입력된다. 점의 좌표는 좌표의 X좌표 위치와 Y좌표의 위치가 공백을 사이에 두고 입력되며, 좌표는 0이상 10,000이하의 정수이다.




입력된 점들의 정보에 대해서 주어진 조건을 만족하는 사각형의 최소 넓이를 출력한다.



2 
100 100 
200 200
4






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