← All solutions

Shortest judge solution: 4669 bytes. Shortest team solution (during contest): 4372 bytes.

This was the only computational geometry problem in the set. We are given a polygon, and asked to find the point inside (or on the boundary of) the polygon that is furthest away from any vertex of the polygon (or rather, we are only asked to find this furthest distance, but we don’t know of any way of finding that without also finding a furthest point). The key conceptual observation to make is the following: the furthest point will lie either (i) on a vertex of the Voronoi diagram of the set of polygon vertices, or (ii) on the intersection of a Voronoi edge with a polygon edge. Here are two examples (the second one being the first sample input, and the first one being one of the secret test cases) illustrating these two possibilities (the blue lines show the Voronoi diagram and the little red asterisk marks the furthest point):

With this easy theory sorted out, it is time to buckle up for the less easy implementation. There are two parts: first we need to compute the Voronoi diagram, and then we have to find the furthest point.

For the first part, there are well-known O(n log n) algorithms for Voronoi diagram, and if you have one of those in your team notebook then you can just go with that, but these algorithms are quite difficult to implement correctly and if you do not happen to have such an implementation available, the input bounds (n ≤ 2000) do allow for something slower and easier. For instance, one can take e.g. Fortune’s O(n log n) algorithm and simplify some steps while keeping it O(n²), or one can take a more direct approach and compute the Voronoi diagram in O(n² log n) time (but in this case one has to be a bit careful with the constant factors in the implementation) by taking each polygon vertex and computing the cell around it in O(n log n) time using a relatively simple circular sweep algorithm similar to the Graham scan algorithm for convex hulls. We make sure to store in our Voronoi diagram which polygon vertices define each Voronoi vertex/edge, so that we can evaluate the distance for each candidate point in O(1) time.

The second part is easier (again owing to the fact that the polygon is relatively small), assuming one has access to basic geometric primitives such as point in polygon and line segment intersection (and if one does not, one should probably have stayed away from this problem in the first place). We simply go over every vertex of the Voronoi diagram, and check if it is inside the polygon (in which case it is a candidate furthest point). Similarly for every edge of the Voronoi diagram we compute all intersections with the polygon edges (and these are also candidate furthest points). This then takes O(n²) time, because there are O(n) Voronoi vertices and edges, and both point in polygon tests and “compute intersection with every polygon edge” also take O(n) time.

Fun fact: this problem was originally proposed with much larger polygons, requiring O(n log n) time, but we felt that this was just too hard, even for the World Finals. In this version, computing the Voronoi diagram in O(n log n) time is actually not the hardest part – the second part of finding the furthest point in the Voronoi diagram is even harder (it can be done using a complicated sweepline algorithm, but one has to be very careful, because the number of intersections between polygon edges and Voronoi edges can be quadratically large, so even enumerating all of them would be too costly).

Another approach than the one described above is to do a binary search on the answer and then try to determine efficiently whether a given circle radius covers the polygon or not. That task can be done in O(n² log n) with a sweepline approach. We also saw at least one team solving the problem with a direct sweepline approach without binary search or explicitly computing the Voronoi diagram, but our impression was that this solution was in some sense implicitly computing the Voronoi diagram and incorporated the second part into it.