통신 가능 범위

휴대폰 사용자가 두 끝점의 좌표가 모두 정수인 직선 선분을 따라 이동한다. 어떤 지점에서 사용자가 통신 가능(coverage) 상태가 되려면, 그 지점이 적어도 하나의 송신탑의 전송 반경 안에 있어야 한다. 사용자가 경로를 따라 이동하는 동안, 어떤 송신탑의 반경 안으로 들어가거나 모든 송신탑의 반경 밖으로 나올 때마다 통신 가능 상태를 얻거나 잃을 수 있다.

최대 $100$개의 송신탑의 위치와 전송 반경이 주어질 때, 경로 전체 길이 중 사용자가 통신 가능 상태인 구간의 비율(백분율)을 구하여라.

모든 $(x, y)$ 좌표는 $[-100, 100]$ 범위의 정수이며, 각 송신탑의 반경은 $[1, 100]$ 범위의 정수이다.

입력은 여러 개의 구성(configuration)으로 이루어지며, 각 구성은 한 줄에 다음과 같은 형식으로 주어진다:

N C0X C0Y C1X C1Y T1X T1Y T1R T2X T2Y T2R ...

여기서 $N$은 송신탑의 개수, $(C0X, C0Y)$는 사용자 경로의 시작점, $(C1X, C1Y)$는 경로의 끝점이다. 각 송신탑 $k$에 대해 $(TkX, TkY)$는 그 위치, $TkR$은 전송 반경이다. 모든 경로의 시작점과 끝점은 서로 다르다.

입력의 끝은 $0$ 하나만 있는 줄로 표시된다:

0

각 구성마다, 경로 중 통신 가능 상태인 부분의 비율(백분율)을 소수점 아래 둘째 자리까지 반올림하여 한 줄에 출력한다.