Editorial for Mock CCC '19 Contest 2 S4 - Tudor Walks Among the Goats
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 candidate lines, giving an 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 .
Comments