Preparing NOJ

Peace Treaty

1000ms 65536K


As part of a peace treaty with the Navi, the humans are allowed mine for Unobtainium in a remote,

deserted area of Pandora. The scientists have identified many possible excavation sites, and are now

trying to figure out where to place the Mining Center. The placement of the mining center is further

constrained by the fact that the robots that will carry the Unobtainium from the excavation sites to

the mining center can only walk along prespecified Grid lines (see figure). The goal is now to find the

location of the mining center so that the maximum distance to the excavation sites is minimized. You

are to write a program for finding that location.

Specifically, you are given the x- and y-coordinates of the excavations sites, (x1, y1), (x2, y2), ...(xn, yn)

(n denotes the number of excavation sites). You are to find the coordinates for the Mining Center,

(x0, y0), so that the maximum of the distances between the mining center and the excavation sites is

minimized. All coordinates must be integers. The distance metric to be used is the rectilinear distance

(also called Manhattan distance). Specifically, the rectilinear distance between (x0, y0) and (xi, yi) is:

|xi − x0| + |yi − y0|

Further, if there are multiple locations which qualify, then you must find the location that is closest

to the origin by Euclidean distance q metric. Since origin is at (0, 0), this corresponds to minimizing


+ y2


In other words, given the input (x1, y1), ..., (xn, yn), your goal is to find (x0, y0) such that:



(|xi − x0| + |yi − y0|)

is minimized, and if there are multiple answers, then



+ y2

0 is the smallest among all such answers.


The first line in the test data file contains the number of test cases, n. After that, each

line contains one test case. The test case begins with the number of mines, followed by the x and y

coordinates of each mine. All coordinates must be integers. Very large coordinate values may be used

(million+), so brute force methods will not work.


For each test case, you are to output a line beginning with ”LOCATION”, followed by the

x and y coordinates of the mining center. All coordinates must be integers.

Sample Input:

4 100 0 40 0 -10 0 20 0
3 245 692 -772 -647 330 526

Sample Output:

LOCATION -121 -120






Provider NOJ

Code NOJ1396


Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10


Nothing Yet