← All solutions

Shortest judge solution: 3480 bytes. Shortest team solution (during contest): 4026 bytes.

This problem is conceptually simple: simply run a ternary search for the answer, but the details makes it a bit difficult to implement this correctly.

The first detail to resolve is that we want to figure out if the polygons never intersect or touch. Since it can be the case that the two asteroids just touch in a single vertex for a single time step, we need to be a but careful here, and the safest course is to use exact, integer arithmetic, when checking if the two polygons ever touch.

The second detail to resolve is: for a given time t, what is the overlap area at this time? This boils down to computing the intersection of two convex polygons. In general, polygon intersection is pretty messy, but for convex polygons, one can use the following approach. The vertices of the intersection are: (i) the vertices of polygon 1 that are contained in polygon 2, (ii) the vertices of polygon 2 that are contained in polygon 1, and (iii) the intersection points of the edges of the two polygons. To compute the order in which these vertices come, we can sort them by angle around the center of mass of the intersection polygon (the center of mass is simply the average of the points). Now we have the intersection polygon and can compute its area.

The last (but minor) detail to resolve is that the intersection area can be constant and maximum for a time period, and we want to find the smallest time this happens. So if in the ternary search we look at times t₁ < t₂ and encounter two intersection areas that are the same (up to some small ε error from floating point computations) we need to make sure to throw out the times > t₂ from our search rather than the times < t₁.