← All solutions

The first step is to figure out what to do in the case when all segments have to be used to form a single polygon. If one plays around with it a little bit, it is pretty natural to guess that in that case the best solution is to put all the vertices on a common circle. To figure out the exact placements of the sticks one then has to compute the radius of this circle. This can be done by a standard bisection search (i.e., real-valued binary search). Some care needs to be taken here, as there are two cases to consider (whether the center of the circle lies inside the polygon or not).

With the single-polygon solution as a toolkit, it is not very hard to solve the full problem, all that needs to be figured out is how to partition the sticks into groups. There is a straightforward O(n³) dynamic programming solution to this, but this is too slow. To make it fast enough, the key insight is the following: if we’re not using all the segments to form a single polygon, we should discard the longest segement. This leads to an O(n²) solution.