DIY Radar

이 문제는 인터랙티브 문제입니다.

Pin은 폐품으로 멋진 기계와 로봇을 만드는 열성적인 발명가입니다. 새 폐품장 작업 로봇을 조립하던 중 Pin은 로봇의 AI를 평소보다 일찍 켜는 실수를 했고, 그 바람에 로봇이 예측할 수 없이 폐품장 안으로 도망쳤습니다.

Pin은 로봇을 되찾으러 폐품장에 들어가고 싶지만, 그 지역은 너무 넓습니다. 로봇은 GPS 추적기가 달리기 전에 도망쳤기 때문에 Pin은 로봇의 정확한 좌표를 모릅니다. 로봇이 있을 만한 곳을 대략이라도 추정할 방법이 있으면 좋겠습니다.

Pin은 로봇의 부품 중 하나에 자율 무선 중계기가 들어 있었다는 사실을 떠올렸습니다. Pin이 특정 무선 신호를 보내면 응답으로 Pin과 로봇 사이의 거리를 최소한 알 수 있습니다. 이 거리는 삼각측량에 쓸 수 있습니다.

Pin의 폐품장은 마주 보는 두 꼭짓점이 $(0, 0)$과 $(100, 100)$에 있는 거대한 정사각형입니다. 폐품 더미 사이에는 정사각형의 변과 평행한 작은 길들이 나 있고, 이 길들은 정수 좌표에서 만납니다. 로봇의 AI는 폐품장 안(경계 포함)의 교차점 하나에 무작위로 자리 잡고 그 근처에서 작동하도록 프로그램되어 있습니다. 불행히도 Pin에게는 불법 개조된 로봇의 보안 알고리즘이 과제를 어렵게 만듭니다. 로봇은 탐색용 무선 신호를 감지할 때마다 인접한 교차점으로 이동합니다. Pin은 로봇이 처음 있던 교차점을 찾은 뒤, 그 주변의 여러 교차점을 차례로 탐색하는 편이 더 쉽고 합리적이라고 판단했습니다.

Pin은 로봇의 위치를 알기 전에는 폐품장에 들어가고 싶지 않으므로, 로봇 주변 지역에서 무선을 사용합니다. 다만 Pin은 자신의 사유지를 벗어나지 않습니다. 사유지는 폐품장 경계에서 가로 또는 세로로 1000 이하 떨어진 모든 점을 포함합니다.