← All solutions

This problem is a variant of the so-called kinetic spanning tree problem (though this knowledge is pretty much irrelevant for solving the problem). The main observation is that the only time the minimum spanning tree could possibly change is when the distances d(i₁ , j₁ ) and d(i₂ , j₂ ) between two pairs of asteroids become equal. Finding these times for two given pairs (i₁ , j₁ ) and (i₂ , j₂ ) just amounts to solving a quadratic equation. Thus, there are at most 2 · C(C(n, 2), 2) ≤ 1 499 400 possible times when the spanning tree switches.

We go through these times in increasing order of time. Consider a time t at which two pairs (i₁ , j₁ ), (i₂ , j₂ ) become equidistant. If exactly one of the two pairs, say (i₁ , j₁ ) is an edge in the current spanning tree, there is a possibility that it is switched for (i₂ , j₂ ) at time t (this happens exactly if (i₁ , j₁ ) is on the path from i₂ to j₂ in the current tree, and d(i₂ , j₂ ) becomes smaller than d(i₁ , j₁ ) after time t). The easiest way to check this is to simply recompute the spanning tree at time t + 0.5 · 10⁻⁶ and see if it changed (the problem statement guarantees that the MST can not change more than once in the interval between t and t + 0.5 · 10⁻⁶ ).

In principle this gives an O(n⁶ ) solution (if using a quadratic MST implementation), but it should be pretty clear that the check for whether one of the pairs is in the tree cuts down actual runtime bound significantly—heuristically one would only have to consider at most O(n³ ) of the O(n⁴ ) candidate switch times. Incidentally, it seems very hard to create cases where the answer is more than a few hundred (at least we didn’t figure out how to do it).