Being Solarly Systematic

This problem asks us to collide planets on a euclidean torus until no more can collide.

The equations of each planet are provided parametrically, that is

• x = X(T)
• y = Y(T)
• z = Z(T)

Finding the intersection time of of any two planets boils down to finding the first T at which X1(T) = X2(T), Y1(T) = Y2(T), and Z1(T) = Z2(T). This can be done by solving for the minimum T in each dimension, and then taking the least common multiple (possible because the intersections will be regular and periodic due to the toroidal global topology). Note that the intersections must also be integral, so we must multiply by 1/(T-floor(T)). Note that all numbers are rational, and so assuming there is some collision time, there must be SOME future collision which is integral.

Computing the intersection in each dimension is complicated by the modular topology. The equation we will have to solve is

X1(T) = X2(T) + kD(x), where k is an arbitrary constant, and D(x) is the length of the toroid in the x direction.

We can find one solution for T by assuming k == 0 and solving for T. There is no guarantee, however, that this value is the minimum intersection point, or even positive. To deduce that, we need the interval between that and the next intersection time. This can be found by solving for T when k = 1 and subtracting the two solutions. Note that we should catch parallel lines here (planets have same velocity but different displacements).

Now that we have a period, we can mod any solution we have by that period to come up with the minimum time period at which the two planets will coincide on the X axis. As previously described, this method is combined with the solutions of all dimensions to come up with the earliest intersection time.

Using this, the rest of the algorithm is easy:

1. compute the minimum collision time of all pairs of planets, store in a tree set
2. pop the minimum collision time off the tree
3. remove any future collisions those two planets might have caused with the other planets
4. calculate the new collision times of the new planet with all the remaining planets, storing back in tree set
5. repeat until no collisions are possible

First step requires O(n^2) comparisons. There are O(n) possible collisions which actually occur. Each Collision incurs O(nlogn) time: logn for each treeset access, and n other planets to compute intersections with. This yields overall runtime of O(n^2logn), which is plenty fast.