50147. Circles

I'm a slow walker, but I never walk backwards.

Task Description

We have points on a 2-D plane and all their coordinates are integers. Now we need to find the circle centered at the origin (0, 0) that goes through the maximum number of the given points. Note that there could be multiple points at the same location. If there are multiple circles that have the maximum number of points, report the one with the largest radius. Note that you do not need to compute the square root square to calculate the distance to the origin. You can just compare the square of the radius, which gives the same result as comparing the radius.

Input Format

The first line includes a positive integer $N$ as the number of points on 2-D plain. Then each of the following $N$ lines has two integers $x$ and $y$ as the x and y coordinate of a point.

  • $N \leq 1000100$

Output Format

Output the square of radius of the circle that has the maximum number of points.

Subtasks

  • 10 points: Every circle has exactly one point.
  • 40 points: The circle having the most number of points is unique.
  • 50 points: None of the previous simplification is true.

Notes

The number of points in all subtasks is so large that you have to use qsort(). Note that you only need to sort the points according to the squares of the distance to the origin.

Sample Input 1

5
1 3
2 1
1 4
2 2
1 1

Sample Output 1

17

Sample Input 2

5
3 1
2 2
1 3
1 3
1 1

Sample Output 2

10

Sample Input 3

5
5 0
3 4
0 -17
-15 8
1 1

Sample Output 3

289

Discussion