레이팅 미적용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.
Interaction This is an interactive problem. Your submission will be run against an interactor, which reads the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:
The interactor first sends an integer \(n\) (\(1 \le n \le 7\)), the number of Dragon Balls you still need to find. The \(n\) balls are hidden at integer locations \((x,y)\) with \(0 \le x,y \le 10^6\). Your submission may not guess outside this area.
Your submission then repeatedly sends such an integer location \((x,y)\) and the interactor replies with an integer \(d\) (\(0 \le d \le 2\cdot 10^{12}\)), the square of the distance from \((x,y)\) to the closest remaining ball.
If \(d = 0\), the ball at \((x,y)\) is considered found and ignored in further guesses. When all balls are found, your submission should exit. Each location holds at most one ball.
Make sure you flush the buffer after each write.
A testing tool is provided to help you develop your solution. Interaction
1
4 3
2
4 3
5 5