Dragon Balls

시간 제한1초메모리 제한1024 MB

요약

어떤 점을 질의하면 숨겨진 점 일곱 개 중 가장 가까운 점까지의 거리를 알려주는 오라클이 있을 때, 질의를 1000번 이하로 사용해 일곱 점을 모두 찾아야 한다.

난이도: 보통10점 중 7점
유형: 기하, 수학, 분할 정복, 이분 탐색
정답자: 아직 제출이 없습니다

문제

During the showdown with Frieza on Namek, Krillin died yet again and needs to be brought back to life using the Dragon Balls. As everybody else is still busy fighting Frieza, the task of retrieving all seven Dragon Balls has fallen to you.

The balls are hidden at unknown locations in a 2D plane and you have been handed a Dragon Radar, designed by Bulma, that you must use to locate them. You can repeatedly fly to arbitrary locations, and the radar will then inform you about the distance to the closest Dragon Ball. If this distance is $0$ this means that you found one of the balls and you can then recalibrate the radar so that it ignores the ball you just found.

With the battle still going on, and the radar having limited energy, you are obviously in a great hurry. You need to make sure to collect all the balls by using the radar no more than $1\\,000$ times.

예제2

예제 1
입력
```
1

25

2

0
```
예상 출력
```
0 0

3 4

4 3
```
예제 2
입력
```
2

8

0

1

0
```
예상 출력
```
2 1

5 5

4 2

4 3
```