SOJ ONLINE JUDGE

가장 먼 두 점

난이도: Platinum III 출제자: rlatjwls7882 시간 제한: 1000 ms 메모리 제한: 512 MB
기하학볼록 껍질회전하는 캘리퍼스

평면 위에 $N$개의 점이 있다. 서로 다른 두 점 사이의 거리의 제곱의 최댓값을 출력하라.

입력

첫 번째 줄에 점의 개수 $N$이 주어진다. $(3 \leq N \leq 200\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 점의 좌표 $x$, $y$가 주어진다. $(-10^9 \leq x,y \leq 10^9)$

같은 좌표를 가진 점은 두 번 이상 주어지지 않으며 한 직선 위에 있지 않은 세 점이 존재한다.

출력

서로 다른 두 점 사이의 거리의 제곱의 최댓값을 출력한다.

예제 입력 1

6
0 0
4 0
4 3
0 3
2 1
1 2

예제 출력 1

25

제출