Robert Hood

Time limit1sMemory limit256 MB

Summary

Given C points on a plane, compute the squared distance between the farthest pair of points.

Level: Medium6 of 10
Topics: Geometry, Sorting, Two pointers
Solved: No attempts yet

Problem

Robert Hood is Robin Hood's younger brother. He practices archery because he wants to become a legend like his brother.

This time the archery contest held in Nottingham follows different rules from modern archery. In modern archery the person with the higher score wins. In the Nottingham contest the winner is the person with the largest maximum distance between two of their arrows on the target.

Robert Hood shot $C$ arrows and every one of them hit the target. The target is a two dimensional plane and each arrow is a point. Given the coordinates of the arrows, write a program that finds the square of the distance between the two farthest arrows.

Input

The first line contains the number of arrows Robert Hood shot, $C$ ( $2 \le C \le 100\,000$ ). Each of the next $C$ lines contains the coordinates $x$ and $y$ of one arrow, separated by a space. The coordinates are integers and their absolute values do not exceed $1\,000$ . Several arrows can land on the same spot.

Output

Print the square of the distance between the two farthest arrows. The coordinates are integers, so this value is always an integer. Print it without a decimal point.

Examples2

Example 1
Input
```
2
2 2
-1 -2
```
Expected output
```
25
```
Example 2
Input
```
5
-4 1
-100 0
0 4
2 -3
2 300
```
Expected output
```
100404
```