공장 로봇

예제 설명. 임계 거리는 입력에 있는 기둥 1와 2 사이의 거리이다. 두 기둥의 중심점 사이 거리는 약 405.123이고, 두 기둥 사이의 실제 거리는 405.12 - 110 - 30 = 265.12이므로 로봇의 최대 반지름은 265.12/2 = 132.56이다.

크기가 $1000 \times 1000$미터인 넓은 공장 바닥에 반지름이 제각각인 원형 기둥들이 있다. 기둥들은 서로 또는 벽과 맞닿아 있지 않다. 공장을 소유한 회사는 내부를 돌아다닐 경비 로봇을 구매할 계획이다. 공장 내부의 네 모서리에는 기계가 배치되어 있으며, 로봇은 기둥과 벽 사이를 지그재그로 지나 이 기계들에 도달할 수 있어야 한다. 시중에서 판매되는 경비 로봇은 기둥과 마찬가지로 모두 완전한 원형이다. 하지만 회사는 로봇을 구매하기 전에 회사의 요구 사항을 여전히 충족할 수 있는 로봇 반지름의 최댓값을 알고자 한다.

로봇의 어떤 부분도 공장 밖으로 나가서는 안 된다. 로봇의 반지름이 $r$이면 로봇은 각각 점 $(r, r)$, $(1000 - r, r)$, $(r, 1000 - r)$, $(1000 - r, 1000 - r)$에 도달하여 그곳에서 네 기계를 관리할 수 있어야 한다. 기계는 로봇의 이동을 절대로 방해하지 않는다.

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$20$| $n = 1$

$2$ |$80$| 추가 제한 없음.

첫째 줄에 공장 내부의 기둥 수를 나타내는 정수 $n$ ($1 \le n \le 50$)이 주어진다.

이어서 각각 3개의 정수 $x$, $y$, $r$을 포함하는 $n$개의 줄이 주어진다. 이 수들은 기둥 하나의 중심 좌표와 그 반지름을 나타낸다.

로봇의 최대 반지름을 나타내는 실수 하나를 출력한다. 출력한 답과 심사위원의 답의 차이가 $0.01$보다 작으면 정답으로 인정된다.