|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||1024 MB||0||0||0||0.000%|
You have gone on a hiking trip, but now you are getting tired and would like to return home. As a precaution, you always take your mobile phone with you, so you can call for help in case of an emergency. However, it only works as long as you stay in range of (one of) the phone towers in the area. Fortunately, you know precisely where you are and where you are going, and you brought a map of the area showing the locations of the mobile phone towers. You want to take the shortest route home, while staying in range of at least one of those towers.
On the first line an integer t (1 ≤ t ≤ 100): the number of test cases. Then for each test case:
All locations consist of two space-separated integer coordinates x and y (1 ≤ x, y ≤ 1 000).
All locations in the input for a single test case will be distinct. The starting locating will not be more than d units away from the nearest tower.
For each test case:
Your answer should have either an absolute or a relative error of at most 10−6.
1 2 3 1 1 8 2 2 2 4 4 7 3