Editorial for COCI '13 Contest 6 #4 Kružnice
Submitting an official solution before solving the problem yourself is a bannable offence.
Since the circles do not intersect, we can look at them as intervals. More specifically, we observe their intersection with the -axis.
Let us construct a relation contains such that contains if interval is inside of interval , with allowed touching on the edges.
Let us construct a relation directly_contains such that directly_contains if contains and there is no other circle for which holds that contains and contains .
Intuitively, directly_contains if is one of the first smaller circles in .
Because there is at most one circle that directly_contains an arbitrary circle, this relation is a tree.
Every circle will increase the number of regions by or . In the case when a circle directly contains more other circles which touch along all its length, that circle is going to increase the solution by . In the other case, by .
The tree of circles can be built using the sweep algorithm where an event is at the beginning or end of a circle. The events are processed by their coordinates. As the structure of the sweep algorithm, we will use a stack which keeps track of the current parent circle and whether we have lined up every directly contained circles next to each other. In the moment of popping a circle from the stack, the solution is increased by if all the directly contained circles are lined up next to each other. In the other case, the solution is increased by . The final solution needs to be incremented by because it represents the whole region above all the circles.
The complexity of the algorithm is where is the number of circles.
Comments