### PROBLEM LINKS

### DIFFICULTY

EASY

### EXPLANATION

Consider the cones and circles as vertices of a graph, where the edge between any 2 vertices has length equal to the distance between the corresponding elements of the obstacle course. Note that the longest edge in the graph is the one that connects the edges corresponding to the 2 circles. Our goal is to partition the vertices of the graph into 2 sets representing the “inside” and “outside” of the car’s path, so that the distance between any two vertices from different sets is at least the diameter of the car. We do this by constructing the minimum spanning tree (MST) of the graph, then removing the longest edge on the path from the outer edge of the track to the inner edge. Because the spanning tree is minimal, no two verticies from different sets can have an edge longer than the removed edge. Because there exists a path from the outer circle to the inner circle consisting only of edges not exceeding the length of the removed edge, there cannot be a partition which is separated by a longer distance. Therefore the length of the removed edge is the maximal diameter.

The MST can be easily computed in O(N^{2}) time using Prim’s algorithm, though a O(N^{2}log N) algorithm such as Kruskal’s will suffice. Both Prim’s and Kruskal’s can be modified to compute the length of the edge in question without actually computing the MST itself. Because the graph is mostly Euclidean, a more complicated O(N log N) solution also exists.