평평한 나라에서 그늘 찾기
시간 제한1초메모리 제한128 MB
공원 안에 서로 겹치지 않는 원 N개가 주어질 때, 원점을 중심으로 회전하는 태양에서 나온 광선이 각 원에서 잘라내는 현 길이의 합을 1440번 측정해 최댓값을 구한다.
문제
평평한 나라(Flatland)는 언제나 맑아서 짜증이 날 정도다. 그래서 Alex는 그늘을 찾아 공원으로 향한다.
공원은 좌표평면의 원점을 중심으로 하는 한 변의 길이가 인 정사각형이며, 꼭짓점은 이다. 공원 중앙(원점)에는 점 크기의 벤치가 있고, Alex는 여기에 앉는다. 태양은 원점을 중심으로 하고 반지름이 인 원 위를 시계 방향으로 도는 점이다. 자정에 태양은 에 있으며, 한 바퀴를 도는 데 시간이 걸린다.
공원에는 그늘을 드리우는 나무가 여러 그루 있다. 각 나무는 중심 좌표와 반지름이 모두 정수인, 속이 꽉 찬 원이다. 태양에서 벤치로 향하는 햇빛 광선을 생각하자. 어느 순간의 그늘 값은, 그 광선이 각 나무를 지나며 잘라내는 현(chord)의 길이를 모든 나무에 대해 더한 값이다. 즉, 햇빛이 태양에서 벤치에 도달하기까지 통과해야 하는 나무의 총 길이다. (벤치를 기준으로 태양의 반대편에 있는 나무는 이 햇빛을 가리지 못하므로 값에 기여하지 않는다.)
자정부터 시간 동안 매 분 정각마다, 즉 00:00, 00:01, ..., 23:59의 총 번 그늘 값을 측정한다. 이 값들의 최댓값을 구하여라.
입력
입력은 여러 개의 테스트 케이스로 이루어진다(최대 개). 각 테스트 케이스는 나무의 수를 나타내는 정수 ()이 적힌 한 줄로 시작한다. 이어지는 개의 줄에는 각각 세 정수 , , 가 주어지며, 이는 번째 나무의 중심 좌표와 반지름이다.
마지막 테스트 케이스 다음에는 하나만 적힌 줄이 온다.
어떤 나무도 다른 나무를 포함하거나 교차하지 않는다(두 나무가 접할 수는 있다). 또한 어떤 나무도 공원 밖으로 나가지 않으며, 벤치를 포함하거나 벤치에 접하지도 않는다.
출력
각 테스트 케이스마다 그늘 값의 최댓값을 소수점 아래 셋째 자리까지 정확히 반올림하여 한 줄에 하나씩 출력한다.