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

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

#1482 upload 5 done 4 how_to_reg 4

최소 포함 사각형 timer 1s memory - MB

#1482

최소 포함 사각형 1s - MB