The farthest pair
Given points on a plane, find two between which the distance is the largest, and print the square of that distance: for integer coordinates it is an integer. There are up to two hundred thousand points, so trying all pairs will not work. One of the tests is all earthquakes of magnitude five and above for 2015–2025 (the USGS catalogue, coordinates in hundredths of a degree).
Input
The first line holds n (1 ≤ n ≤ 200,000), then n lines with integers x, y (|x|, |y| ≤ 10⁹). Points may coincide.
Output
The largest squared distance between two points (0 if there is one point or all coincide).
Examples
Example 1
5 0 0 4 0 4 3 0 3 2 1
25
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Can one of the two farthest points lie strictly inside the convex hull?
2Hint 2
A hull can have many vertices: sixty thousand in the sixth test. For each side of the hull, find the vertex farthest from the line of that side. How does this vertex change when the side moves on by one?
3The idea
The farthest pair is two vertices of the hull: if a point is inside, it can be moved away from the other point without leaving the hull, and the distance grows. Trying pairs of vertices is still expensive, but rotating calipers help: go along the sides of the hull in order and keep a pointer to the vertex farthest from the current side. On moving to the next side this pointer only moves forward: two pointers going round a circle.
4Walkthrough
Build the hull with the monotone chain. If there are one or two vertices, the answer is obvious. Otherwise for each side (a, b) move j forward while the area of the triangle (a, b, hj+1) is greater than the area of (a, b, hj), that is, while the next vertex is farther from the line ab. The areas are compared with a cross product, without division. The candidates for the answer are the pairs (a, hj) and (b, hj).
Why the pointer goes round the circle only once: for a convex polygon the distance from the vertices to the line of a side first grows and then decreases, and as the side turns, the maximum moves in the same direction. In all i makes h steps and j at most 2h.
4+Solution
5Complexity
O(n log n) for the hull and O(h) for the calipers. The squared distance is at most 2·(2·10⁹)² = 8·10¹⁸, which fits in an int64.
6Common mistakes
- Trying pairs of hull vertices. For random points the hull is small, and trying pairs passes. But the sixth test is points on a parabola, and all sixty thousand are vertices.
- The square root of the square. The squared distance is what must be printed: that way the answer is exact.
- Stopping the calipers with “≥”. If the pointer moves on equal areas, it can go round the circle an extra time on parallel sides. A strict “>” is safe.