Coverage#3134
A cell phone user moves along a segment with endpoints having integer coordinates. To have cell phone coverage, the user must be within the transmission radius of at least one tower. As the user travels along the path, coverage can be gained by entering the radius of a tower, or lost by leaving the radii of all towers. Given the locations of up to towers and their radii, calculate the percentage of coverage the user has along the specified path. The coordinates are integers between and inclusive, and tower radii are integers between and inclusive.
Each line contains one test case in the format: n\ c_0x\ c_0y\ c_1x\ c_1y\ t_1x\ t_1y\ t_1r\ t_2x\ t_2y\ t_2r\ \ldots Here is the number of towers, (c_0x,\ c_0y) is the starting point of the user's path, (c_1x,\ c_1y) is the endpoint, (t_kx,\ t_ky) is the position of the -th tower, and t_kr is its transmission radius. The start and end points are distinct. The final line contains .
For each configuration, output a line containing the percentage of coverage the cell phone has, rounded to two decimal places.
Example 1