듣고 있나?
면접 대비시간 제한2초메모리 제한512 MB
자신의 좌표와 n개의 청취 원이 주어질 때 원점에서 최대 두 개와 겹치는 최대 방송 반경의 정수 내림값을 구합니다. 이미 세 개 이상에게 잡히면 0을 출력합니다.
문제
당신은 적진 뒤 secret location에 있는 최고의 정부 요원이다 (우와....짜릿하다!). 당신에게는 함께 일하는 여러 요원과 연락을 유지할 수 있는 통신 장치가 있다. 이 장치의 방송 범위는 조절할 수 있으며, 이상적으로는 최대값으로 설정해 최대한 많은 요원에게 닿고 싶다. 불행히도 적도 바보가 아니라서, 당신의 신호를 탐지할 수 있는 도청 장치들을 가지고 있다. 각 도청 장치는 고정된 범위를 가지며(장치마다 다를 수 있다), 당신의 위치를 정확히 파악하려면 적은 최소 세 개의 도청 장치에서 당신을 탐지해야 한다. 따라서 최대 두 개의 도청 장치만 당신을 탐지하도록 방송 범위를 설정하는 한 안전하다. 도청 장치는 당신의 방송 범위와 그 장치의 탐지 범위가 한 점보다 많이 만나면 당신을 탐지할 수 있다.
예시 상황이 아래에 나와 있다. 당신의 장치와 그 방송 영역은 회색 원으로, 네 개의 도청 장치와 그 탐지 영역은 흰색 원으로 표시되어 있다. 맨 왼쪽에서는 어떤 도청 장치도 당신을 탐지할 수 없도록 방송 범위를 설정했지만, 분명히 범위를 늘릴 수 있다. 가운데 그림에서는 두 개의 도청 장치가 당신을 탐지할 수 있도록 범위를 늘렸지만, 이 정도는 괜찮다. 오른쪽 그림에서는 이제 세 개의 도청 장치가 당신을 탐지할 수 있으므로 범위를 너무 많이 늘린 것이다.
당신의 위치와 여러 도청 장치의 위치 및 탐지 범위가 주어졌을 때, 통신 장치의 최대 방송 범위를 구하라. 이 범위는 방송 장치가 이미 세 개의 도청 장치 범위 안에 있다면 0일 수도 있다.
입력
입력은 세 정수 cx cy n이 있는 한 줄로 시작한다. 여기서 (cx, cy)는 당신의 위치이고, 3 ≤ n ≤ 100은 도청 장치의 수이다. 다음 n개의 줄 각각에는 세 정수 x y r이 있다. 여기서 (x, y)는 도청 장치의 위치이고, 0 < r ≤ 1 000은 그 탐지 영역의 반지름이다. 모든 좌표는 −1 000과 1 000 사이이다. n + 1개의 모든 위치는 서로 다르다.
출력
최대 방송 영역의 반지름을 가장 가까운 정수로 내림하여 출력하라.