|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||47||17||16||34.783%|
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 (XR,YR) measures its distance to a beacon at (XB,YB), it thus obtains the Manhattan distance: |XR − XB| + |YR − YB|.
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, Xi, Yi, and Di, such that −106 ≤ Xi, Yi ≤ 106 and 0 ≤ Di ≤ 4·106. The pair (Xi, Yi) 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, XR and YR, 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”.
3 999999 0 1000 999900 950 451 987654 123 13222
2 100 0 101 0 200 199
2 100 0 100 0 200 199
2 0 0 5 10 0 6