Go Rafting   goraft.txt

Farmer John has decided to take his cows on a whitewater rafting trip
down the Colorado River. However, he's afraid that his larger rafts
will get stuck between the N (0 <= N <= 2,500) rocks in the river. In
order to maximize the number of cows he can take on the trip, he wants
to know the diameter of the largest circular raft that will fit
between the rocks.

The river is W (1 <= W <= 30,000) meters wide, with the banks at X = 0
and X = W. The rapids begin at Y = 0, and continue in the positive Y
direction. Since FJ's cows are such strong paddlers, the raft is
allowed to move backwards if necessary.

The rocks will never overlap the banks or each other, though they may
touch.

PROBLEM NAME: goraft

INPUT FORMAT:

* Line 1: Two integers, W and N

* Lines 2..N+1: Three space-separated integers X (0 < X < W), Y (0 < Y
        < 30,000), and R (1 <= R <= W/2), representing the location
        and radius of a rock.

SAMPLE INPUT:

11 5
2 3 2
8 3 1
9 7 1
3 9 3
8 1 1

OUTPUT FORMAT:

* Line 1: The diameter of the largest circular raft that will fit
        through the rocks, printed to two decimal places.

SAMPLE OUTPUT:

2.32