Catching Shade in Flatland

Time limit1sMemory limit128 MB

Summary
Given N disjoint circles inside a park, track a ray from a sun rotating around the origin and report the maximum total chord length cut through all trees over 1440 one-minute samples.
Level

Hard8 of 10

Topics
Geometry, Math, Simulation, Brute force
Solved
No attempts yet

Problem

It is always sunny in Flatland, which gets annoying, so Alex heads to a park to catch some shade.

The park is a square of side 400400 centred at the origin of the Cartesian plane, with vertices at (±200,±200)(\pm 200, \pm 200). A point-sized bench sits at the centre of the park (the origin), where Alex sits. The Sun is a point that travels clockwise along the circle centred at the origin with radius 500500. At midnight the Sun is at (0,500)(0, 500), and it takes 2424 hours to complete one full revolution.

Several trees in the park provide shade. Each tree is a solid circle with integer centre coordinates and integer radius. Consider the ray of sunlight that travels from the Sun to the bench. Its shade value at a given moment is the sum, over all trees, of the length of the chord cut from each tree by that ray — that is, the total length of tree the sunlight must pass through on its way from the Sun to the bench. (A tree lying beyond the bench, on the far side from the Sun, does not block this sunlight and contributes nothing.)

We measure the shade value once every minute, on the minute, over a 2424-hour period starting at midnight: at 00:00, 00:01, ..., 23:59 (14401440 measurements). Determine the maximum of these shade values.

Input

The input contains several test cases (at most 100100). Each test case begins with a line containing an integer NN (1≤N≤2001 \le N \le 200), the number of trees. Each of the next NN lines contains three integers xix_i, yiy_i, rir_i — the centre coordinates and radius of the ii-th tree.

The last test case is followed by a line containing a single 00.

No tree contains or intersects another (two trees may touch), and no tree extends outside the park. No tree contains or touches the bench.

Output

For each test case, print on its own line the maximum shade value, rounded to exactly 33 decimal places.

Examples1

  1. Example 1

    Input
    1
    50 0 10
    2
    30 0 10
    60 20 20
    0
    
    Expected output
    20.000
    53.036