Editorial for Mock CCC '19 Contest 2 S4 - Tudor Walks Among the Goats


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Note firstly that there exists an optimal line which is tangent to at least two circles - any optimal line that is only tangent to one circle can be rotated so as to be tangent to another one.

Note that there are four possible lines that can be drawn which are tangent to two given circles. The math for this is left as an exercise to the reader.

To solve the subtask, enumerate every possible candidate line per the above and check how many circles each one intersects. There are \mathcal O(N^2) candidate lines, giving an \mathcal O(N^3) algorithm.

For full credit, fix a given circle. For every other circle, find all points on the circle such that, when a tangent line is drawn through the given point, it intersects the other circle. These form intervals on the circles. We then need to solve the problem of having intervals on a circle and needing to count the point that is inside the maximum number of intervals, which can be done with an angle sort. This approach is \mathcal O(N^2 \log N).


Comments

There are no comments at the moment.