← All solutions

We construct the following graph: the vertices are all the airports, together with all intersection points between the “safety circles” around the airports (i.e., all points that are at distance R from two airports). There are at most 2 · C(N, 2) ≤ 600 such intersection points. There is an edge between two points if the great circle arc between the two points lies completely inside the allowed flight region (i.e., the union of the “safety circles”).

The main difficulty of the problem lies in constructing this graph, after that it is fairly straightforward graph problem which we leave to the reader. First, we need to find the intersection points, i.e., compute the intersections of two circles in 3D. which is a bit messy. Second, we need to check if the arc between two points lies inside the allowed flight region. This can be done by again using circle-circle-intersections to compute which part (if any) of the arc is covered by each airport, and then computing the union of all these parts. This gives an O( N ⁵ log N ) algorithm (though since N is so small, using a quadratic interval union which gives an O( N ⁶ ) solution works fine).