Under construction

Still being built. Things may change

Viva Confetti

Time limit2sMemory limit512 MB

Summary
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 nn in it, a positive integer not greater than 100. Each of the next nn 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 ±5×10−13\pm 5 \times 10^{-13}. Changing an input value by less than 5×10−135 \times 10^{-13} never changes which discs are visible.

The coordinates of every point contained in a disc are between −10-10 and 1010.

The discs are listed in stacking order. x1 y1 r1x_1\ y_1\ r_1 is the bottom disc and xn yn rnx_n\ y_n\ r_n 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.

Examples3

  1. Example 1

    Input
    3
    0 0 0.5
    -0.9 0 1.00000000001
    0.9 0 1.00000000001
    5
    0 1 0.5
    1 1 1.00000000001
    0 2 1.00000000001
    -1 1 1.00000000001
    0 -0.00001 1.00000000001
    5
    0 1 0.5
    1 1 1.00000000001
    0 2 1.00000000001
    -1 1 1.00000000001
    0 0 1.00000000001
    2
    0 0 1.0000001
    0 0 1
    2
    0 0 1
    0.00000001 0 1
    0
    
    Expected output
    3
    5
    4
    2
    2
    
  2. Example 2

    Input
    1
    0 0 1
    2
    0 0 1
    0 0 2
    2
    0 0 2
    0 0 1
    0
    
    Expected output
    1
    1
    2
    
  3. Example 3

    Input
    2
    0 0 1
    1 0 1
    3
    -1 0 1
    1 0 1
    0 0 1
    0
    
    Expected output
    2
    3