시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 339 54 21 12.139%

문제

좌표 평면에 N (4<=N<=1,500) 개의 점이 주어진다.

서로 다른 점 4개를 선택하면 사각형을 만들 수 있다. 이러한 사각형 중에 직사각형인 것 중 넓이가 가장 큰 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 점의 좌표 x y가 주어진다. 점의 좌표는 -10^8보다 크거나 같고, 10^8보다 작거나 같은 정수이다. 점의 좌표는 중복되지 않는다.

출력

가장 큰 직사각형의 넓이를 출력한다.

예제 입력

8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1

예제 출력

10

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 4번