Maou is the demon king of some other world consisting of a single peaceful and quiet kingdom with villages that can be mapped as points in a 2-D plane. Bored out of his mind, Maou decided to divide the villages of the kingdom into two conflicting nations and witness the ensuing battles. To maximize chaos, he wants to divide the villages in such a way that the minimum distance between any two villages in the same nation is as large as possible. As a servant of Maou, help him compute this value.
Constraints
All villages are at distinct locations.
Subtask 1 [10%]
Subtask 2 [70%]
Subtask 3 [20%]
No additional constraints.
Input Specification
The first line contains an integer .
The next lines each contain integers and , the coordinates of the -th village.
Output Specification
Since Maou does not like floating point values, output the square of the maximum possible value of the minimum distance between any two villages in the same nation.
Sample Input
9
-2 -2
-1 0
2 3
1 2
0 0
0 -3
-3 1
2 -1
4 -2
Sample Output
8
Explanation
A diagram of an optimal division of the villages in this case is provided above. Red points denote villages in the first nation, whereas blue points denote those in the second nation. The minimum distance between any two villages in the same nation is (for which the square is ), and it can be shown that this is the largest possible distance.
Comments