13467번 - Manhattan Positioning System 다국어

The Manhattan Positioning System (MPS) is a modern variant of GPS, optimized for use in large cities. MPS assumes all positions are discrete points on a regular two-dimensional grid. Within MPS, a position is represented by a pair of integers (X,Y ).

To determine its position, an MPS receiver first measures its distance to a number of beacons. Beacons have known, fixed locations. MPS signals propagate only along the X and Y axes through the streets of the city, not diagonally through building blocks. When an MPS receiver at (X_R,Y_R) measures its distance to a beacon at (X_B,Y_B), it thus obtains the Manhattan distance: |X_R − X_B| + |Y_R − Y_B|.

Given the positions of a number of beacons and the Manhattan-distances between the receiver and each beacon, determine the position of the receiver. Note that the receiver must be at an integer grid position (MPS does not yet support fractional coordinates).

The first line contains an integer N, the number of beacons (1 ≤ N ≤ 1000). Then follow N lines, each containing three integers, X_i, Y_i, and D_i, such that −10⁶ ≤ X_i, Y_i ≤ 10⁶ and 0 ≤ D_i ≤ 4·10⁶. The pair (X_i, Y_i) denotes the position of beacon i, while Di is the Manhattan distance between receiver and beacon i.

No two beacons have the same position.

If there is exactly one receiver position consistent with the input, write one line with two integers, X_R and Y_R, the position of the receiver.

If multiple receiver positions are consistent with the input, write one line with the word “uncertain”.

If no receiver position is consistent with the input, write one line with the word “impossible”.