Page not loading? Try clicking here.
Placeholder

#3669

가장 먼 두 점 1 1s 128MB

Problems

2차원 평면에 점이 N개 주어진다. i번째 점은 (x_i\ ,\ y_i)에 있다. 이 때, 가장 먼 두 점의 거리 제곱을 구하여라.​


Input

첫 번째 줄에 점의 개수를 의미하는 자연수 N이 주어진다. (2 ≤ N ≤ 500,000) 두 번째 줄부터 N개의 줄에 점의 위치 (x_i\ ,\ y_i)가 주어진다. (-10^9 ≤ x_i, y_i ≤ 10^9)​


Output

가장 먼 두 점의 거리 제곱을 출력한다.


Example 

9 

-1 -1

3 -3 

6 -6 

-3 -6 

12 0

3 4

-6 3

0 9

6 9
333


You must sign in to write code.