Viva Confetti
Time limit2sMemory limit512 MB
Given n discs stacked in order, count how many discs are visible from above, where a disc counts if some part of it stays uncovered.
- Level
Medium7 of 10
- Topics
- Geometry, Implementation, Brute force, Sorting
- Solved
- No attempts yet
Problem
Confetti are small discs of colored paper that people throw at parties and festivals. People throw a lot of them at once, so the discs pile up on one another and some end up hidden underneath.
Discs of various sizes have been dropped on a table. Given the position and the size of every disc, count how many of them you can see from above. A disc is visible when the part of it that no higher disc covers still has positive area.
The figure below is the first configuration of the first sample input. The bottom disc is still visible.

Input
The input holds several configurations. One configuration has this form.
n
x1 y1 r1
x2 y2 r2
...
xn yn rn
The first line of a configuration is the number of discs in it, a positive integer not greater than 100. Each of the next lines describes one disc: the coordinates of its center and its radius, written as decimal real numbers with up to 12 digits after the decimal point.
The imprecision margin is . Changing an input value by less than never changes which discs are visible.
The coordinates of every point contained in a disc are between and .
The discs are listed in stacking order. is the bottom disc and is the top one. You observe from above.
A line holding a single zero marks the end of the input.
Output
For each configuration, print the number of visible discs on one line.