미스터리 서클
시간 제한2초메모리 제한512 MB
정수 격자점을 중심으로 하는 최대 200개의 단위 원이 주어질 때, 합집합의 넓이를 소수점 네 자리까지 반올림해 구한다.
문제
"호머! 외계인들이 또 나타났어!" 에델과 호머는 직사각형 모양의 밭에서 옥수수를 재배한다. 매년 수확을 앞두고 밭의 일부가 이상한 방식으로(에델의 말에 따르면 외계인에 의해) 짓밟혀 crop이 망가진다. 반지름 1미터인 원 안의 모든 옥수수 줄기는 짓밟히며, 원은 항상 옥수수 밭 안에 완전히 들어간다. 호머는 옥수수 밭 위에 x축과 y축 방향으로 격자점이 정확히 1미터 간격으로 떨어진 2차원 격자를 겹쳐 보면, 원의 중심이 격자점에만 나타난다는 사실을 알아냈다. 다행히 에델과 호머는 미스터리 서클 보험에 가입되어 있지만, 보험금을 청구하려면 파괴된 작물의 총 면적을 신고해야 한다. 미스터리 서클이 겹치는 영역은 총 면적에 한 번만 계산된다.
예시(검은 원은 격자점을 나타낸다).
총 면적 = 5.0548
총 면적 = 6.8402
입력
각 데이터 세트의 첫 줄에는 원의 개수를 나타내는 정수 n이 하나 주어지며, 0 ≤ n ≤ 200이다. 다음 n개 줄에는 각각 원의 중심 좌표를 나타내는 두 정수 x와 y가 공백으로 구분되어 주어진다. 같은 (x, y) 쌍은 이 목록에 한 번만 나타난다. 데이터의 끝은 n = 0인 데이터 세트로 표시된다.
출력
각 데이터 세트에 대해, 위에서 설명한 대로 그 데이터 세트의 원들이 덮는 총 면적을 출력한다. 면적은 소수점 네 자리로 반올림해야 한다. Sample Output에 나온 형식을 따른다. 출력 줄 사이에는 빈 줄을 하나 둔다. π는 3.1415926535로 근사한다.