Problem - 3384

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, (x₁, y₁), (x₂, y₂), ...(x_n, y_n) (n denotes the number of excavation sites). You are to find the coordinates for the Mining Center, (x₀, y₀), 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 (x₀, y₀) and (x_i, y_i) is:

|x_i - x₀| + |y_i - y₀|
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

In other words, given the input (x₁, y₁), ..., (x_n, y_n), your goal is to find (x₀, y₀) such that:

is minimized, and if there are multiple answers, then

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.

Locate Mining Center