Problem G
Forest for the Trees

You have sent a robot out into the forest, and it has gotten lost. It has a sensor that will detect all the trees around itself regardless of any occlusions, but unfortunately in this forest, all trees look alike. You do have a map of all trees in the forest, represented as $(x,y)$ points. Conveniently, since this used to be a tree farm, all trees are at integer coordinates, though not all coordinates are occupied. The robot’s sensor tells you the $x$ and $y$ distance to each tree within range, relative to the front of the robot. However, the robot is heading in an unknown direction relative to the map, so each sensor reading is given as a tuple of (distance to the right of the robot, distance forward of the robot) and either value can be negative since the robot can sense in all directions. Helpfully, the robot will always place itself at integer coordinates and aligned to the positive or negative $x$ or $y$ axis, and will never be at the same location as a tree. Can you find out where the robot is?


The first line of input contains three integers: $n_ t$, the number of trees in the forest, $n_ s$, the number of trees sensed by the robot, and $r_{max}$, the maximum Manhattan distance (sum of $x$ and $y$ distances) of any sensor reading. The next $n_ t$ lines each contain two integers representing the $(x,y)$ locations of all the trees relative to a global coordinate system. The final $n_ s$ lines each contain two integers. The first integer in the $i^{th}$ sensor reading, $s_{i,x}$, represents the distance to the tree along the axis perpendicular to the robot’s heading and the second integer $s_{i,y}$ represents the distance along the axis parallel to the robot’s heading. You can assume that $|s_{i,x}|+|s_{i,y}| \leq r_{max}$ for all $i$. You may also assume $0 < n_ t \leq 5000$, $0 < n_ s \leq 1000$, $0 < r_{max} \leq 1000$, and all tree locations have $x$ and $y$ coordinates $-100,000 \leq x,y \leq 100,000$.


Print one of the following: the $x,y$ location of the robot, printed as two integers separated by a space; “Impossible” if there is no location in the map that could produce the given sensor values, or “Ambiguous” if two or more distinct locations and/or orientations could produce the given sensor values.

Sample Input 1 Sample Output 1
4 4 100
1 1
2 2
2 1
3 3
0 1
0 2
-1 2
-2 3
0 1

Please log in to submit a solution to this problem

Log in