[KOITP] 가장 거리가 먼 두 점(Not Solved)

출    처 : http://koitp.org/problem/FARTHEST_PAIR/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	128 MB	2	1 (50%)	1

문제

2차원 좌표 평면에 $N$개의 점이 주어진다. 좌표가 같은 점이 주어질 수도 있다.

두 점 사이의 거리는 유클리드 거리로 정의한다. 유클리드 거리에서 두 점 $(x_1,y_1)$, $(x_2,y_2)$ 사이의 거리를 $\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$로 정의한다.

이 때, 가장 먼 두 점 사이의 거리를 구하는 프로그램을 작성하시오.

입력

첫 줄에 점의 개수를 나타내는 자연수 $N$이 주어진다. ($2\le N\le 200,000$)

그 다음 $N$개의 줄에 각 점의 $x$, $y$ 좌표를 나타내는 두 정수가 공백으로 구분되어 주어진다. 주어지는 좌표의 절대값은 ${10}^7$을 넘지 않는다.

출력

첫 줄에 가장 먼 두 점 사이의 거리의 제곱을 출력한다.

힌트

입력 예제

5
0 0
0 1
0 2
0 3
0 4

출력 예제

16

점수

아래 4개의 서브태스크로 점수가 매겨진다.

• 서브태스크 1 (30점) : $N\le 1,000$
• 서브태스크 2 (70점) : 별다른 제약 조건이 없다.