PROBLEM LINK:
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM
PRE-REQUISITES:
GEOMETRY, MATHS
PROBLEM:
N(<101) circle painted one after another. When two circles overlap, only the later painted one is fully visible, and the earlier painted one and its boundary are partly obscured by the later painted one. The organizers are interested in knowing the total length of the visible black boundary after all N circles have been painted.
EXPLANATION:
There can be two approaches to this:
APPROACH 1:
We find all the intersection points for each circle, that is, for each circle we find coordinates of all those points where any other circle intersects it. Each circle can have O(N) such points. Now, we sort such points in clockwise or counter-clockwise direction. And for each arc defined by two consecutive points in sorted array, we check if that arc can be counted in answer ie. if that arc lies below any other circle or not*. This checking can be done in O(N). So, overall complexity would be O(N3).
* arc of circle i will lie below circle j(j>i), if that arc lies completely inside circle j.
APPROACH 2:
For i’th circle, for the j’th(0 ≤ j < i) circle, we find intersection points and with respect to a horizontal line, we define the polar angles.
So, we get all information like: i’th circle puts out from the answer the arc defined by angles theta1 to theta2 of circle j.(Note these angles are with respect to some horizontal or vertical line).
After this, we get for each circle all the invalid arcs. There could be atmost O(N) such arcs. Now, some of these might be overlapping, so we merge these interval arcs in O(N log N) using something similar to this.
After merging them into disjoint arc intervals, we find the length of covered boundary and add to answer the remaining length.
So, overall complexity would be O(N*N*log N).
We didn’t go into minute implementation details because that you will get by simple googling. This implementation would be prone to bugs, so a lot of carefulness was required into implementing this.