Where to put a new station
A city has fire stations. It needs a new one, and wants to put it where the nearest station is currently furthest away. The choice is made within one district, a polygon; stations may also stand outside it. Distance is measured in a straight line.
Find the largest distance to the nearest station over all points of the district, inside and on the boundary.
The tests are eight districts of Almaty and the 17 fire stations marked in OpenStreetMap, in metres; for a district consisting of two pieces, the larger is taken.
Input
The first line holds n and m (1 ≤ n ≤ 300, 3 ≤ m ≤ 3000), the number of stations and of district vertices. Then n lines with integer coordinates of the stations, all distinct, and m lines with the vertices of the district in order of traversal. The polygon is simple: its sides do not intersect. All coordinates are at most 106 in absolute value.
Output
One number, the largest distance. The answer is accepted with a relative error of up to 10−6.
Examples
Example 1
2 4 2 5 8 5 0 0 10 0 10 10 0 10
5.830952
Example 2
3 3 1 1 10 1 3 12 0 0 12 0 0 9
5.948297
Limits
- Time · Python
- 16000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 14 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
The distance to the nearest station as a function of the point is simple within one Voronoi zone: there the nearest station is always the same, and the distance grows with distance from it. Where can the maximum be, then?
2Hint 2
Inside the district the maximum can only be where the point cannot be moved away from all its nearest stations at once: at a Voronoi vertex, equidistant from three stations. On the district boundary, at a vertex of the polygon or where a side passes from one zone into another.
3Hint 3
The first sample: a square and two stations at the same height. The corners of the square give 5.39, while the midpoints of the bottom and top sides, where a side passes from one station's zone into the other's, give 5.83. How do you find such points on each side without trying all pairs of stations?
4The idea
Let a point x of the district be neither a Voronoi vertex nor a boundary point. If it has one nearest station p, move x slightly away from p: the distance to p grows, and p stays the nearest. If there are two nearest, p and q, then x lies on their perpendicular bisector, and one can move along it away from both at once. So the maximum is at a Voronoi vertex inside the district or on the boundary. On a side of the polygon the same argument works, except that one can move only along the side: the maximum is at its end or where the nearest station changes.
5Walkthrough
Voronoi vertices. The cell of station i is the intersection of the half-planes “closer to i than to j” over all j; cut a rectangle around the district with them, and the vertices of the resulting polygon are Voronoi vertices (or points on the edge of the rectangle, which are outside the district). The value at a vertex of cell i is the distance to i: it is one of the nearest. Sort the vertices by decreasing value and check whether they lie inside the district only for the first ones, while the value exceeds the answer found so far; the first one inside ends the search. Faster is through the Delaunay triangulation: the Voronoi vertices are the circumcentres of its triangles.
The boundary. On a side ab, start with the station s nearest to a and the parameter t = 0. The point a + t(b − a) becomes closer to station j than to s after crossing their perpendicular bisector, and this crossing is the solution of a linear equation in t. Take the smallest t greater than the current one among the stations we are moving towards, move to it and change s. Each such point and the end of the side is a candidate, and the value there is the distance to the current s.
For the districts of Almaty the answers range from 3 km in the Auezov and Almaly districts to 16.7 km in Bostandyk: there the boundary goes into the mountains.
5+Solution
6Complexity
The cells take O(n2) cuts, each proportional to the number of the cell's vertices (about six on average). Walking the boundary is O(m · n) plus O(n) for each change of zone. The “inside the district” check is O(m), but it hardly ever has to be done. With the Delaunay triangulation the Voronoi vertices are found in O(n log n).
7Common mistakes
- Forgetting the boundary. Only Voronoi vertices and the district's corners: 5.39 instead of 5.83 in the first sample.
- All triples of stations. The centre of the circle through any three stations is not necessarily a Voronoi vertex: a fourth station may be inside the circle. Trying triples with an emptiness check is correct, but it is O(n4).
- Stations outside the district. They affect the distances inside and must not be thrown away: in the thirteenth test the only station is far outside.
- Stations on one line. There are no Voronoi vertices at all, the perpendicular bisectors are parallel, and the answer is entirely on the boundary.