시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 115 | 11 | 7 | 9.589% |
희원이는 지난 몇 년동안 원형 시계를 수집한 수집가이다. 이 시계는 모두 거실의 한 벽에 걸려있다. 이번에 큰 돈을 벌게된 희원이는 시계를 하나 더 사려고 한다. 이때, 벽에 있는 시계의 위치를 건드리지 않으면서 매달 수 있는 가장 큰 시계를 구매하려고 한다.
벽은 너비 W, 높이 H의 직사각형 모양이다. 각 시계의 중심 좌표는 (xi, yi)이고, 반지름은 ri이다. 희원이의 시계는 벽의 경계와 겹치거나 다른 시계와 겹치지 않는다. 하지만, 서로 접할 수는 있다.
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 벽의 너비와 높이 W, H가 주어진다. (1 ≤ W,H ≤ 1,000,000) 다음 줄에는 벽에 걸려있는 시계의 수 C(0 ≤ C ≤ 50)가 주어진다. 다음 C개 줄에는 각 시계의 정보 xi, yi, ri가 주어진다. (ri > 0, 0 ≤ xi - ri, xi + ri ≤ W, 0 ≤ yi - ri, yi + ri ≤ H)
모든 시계의 쌍 i와 j (i ≠ j)는 (xi - xj)2 + (yi - yj)2 ≥ (ri + rj)2 를 만족한다.
각 테스트 케이스에 대해서, 희원이가 구매할 수 있는 가장 큰 시계의 반지름을 출력한다. 정답과의 오차는 10-6까지 허용한다.
1 10 10 4 2 2 1 2 8 1 8 2 1 8 8 1
3.242640687119285
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2010 E번