시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 26 6 6 31.579%

문제

현수는 어떤 좌표 평면에 점을 N개 찍었다. 신기하게도, 모든 점은 음이 아닌 정수 좌표에만 찍혔다.

현수는 직사각형을 하나 그리려고 하는데, 직사각형의 꼭지점은 모두 정수 좌표이고, 모든 변이 X축과 Y축에 평행한 직사각형을 그리려고 한다. 또, 직사각형의 내부에 현수가 찍은 점이 적어도 N/2개가 들어있는 직사각형을 그리려고 한다. 점이 직사각형의 변 위에 놓여져 있는 것은 내부에 있는 것이 아니다.

이러한 직사각형 중에 넓이가 가장 작은 직사각형의 넓이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N이 주어진다. N은 항상 짝수이며, 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 현수가 찍은 점의 정보가 X좌표 Y좌표 순으로 들어온다. 각각의 좌표는 10,000보다 작거나 같은 음이 아닌 정수이다. 모든 점은 중복되지 않는다.

출력

첫째 줄에 현수가 만든 직사각형 중 가장 넓이가 가장 작은 것의 넓이를 출력한다.

예제 입력

6
10 5
11 5
13 5
10 15
11 16
13 17

예제 출력

10

힌트

(9,4), (9,6), (14,4), (14,6)을 꼭지점으로 하는 직사각형을 만들면 된다.

출처