사원

고고학자 팀이 고대 사원에서 발굴을 시작하려 하며, 먼저 현장을 밝혀야 한다. 사원은 넓고 평평한 바닥 위에 여러 개의 높은 원기둥이 서 있는 구조다. 팀은 바닥에 전원 장치 하나와 여러 개의 램프를 놓고, 각 램프를 전원 장치에 가능한 한 짧은 전선으로 연결하려고 한다. 각 전선의 길이를 구하여라.

문제를 단순화하기 위해 다음을 가정한다.

• 어떤 두 기둥도 서로 닿지 않는다.
• 전선은 두께가 없으며, 바닥에 붙어 있어야 하고, 기둥에 닿을 수는 있지만 기둥을 통과할 수는 없다.
• 전원 장치와 램프는 점으로 취급하며, 기둥과 절대 닿지 않는다.

위에서 내려다보면 기둥은 원이고 전원 장치와 램프는 점이다. 각 램프에 대해, 그 램프를 전원 장치에 연결하는 가장 짧은 전선의 길이를 구하는 프로그램을 작성하여라.

첫째 줄에 기둥의 수 $n$ ($1 \le n \le 300$)이 주어진다. 이어지는 $n$개의 줄에는 각 기둥의 정보가 세 정수 $x$, $y$, $r$ ($1 \le r \le 5000$, $r \le x, y \le 10000 - r$)로 주어지며, 이는 기둥의 중심 $(x, y)$와 반지름 $r$을 나타낸다. 다음 줄에 램프의 수 $m$ ($1 \le m \le 200$)이 주어진다. 이어지는 $m$개의 줄에는 각 램프의 좌표 $x_i$, $y_i$ ($0 \le x_i, y_i \le 10000$)가 주어진다. 마지막 줄에는 전원 장치의 좌표 $x_a$, $y_a$ ($0 \le x_a, y_a \le 10000$)가 주어진다.

$m$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 램프를 전원 장치에 연결하는 가장 짧은 전선의 길이를 소수점 아래 정확히 여섯 자리까지 반올림하여 출력한다 (9.278662과 같은 형식).

위 그림은 기둥과 전선의 배치를 보여 준다.