Problem F
Human Observation
It is known by all that the *creepy* Lord Pooty loves observing people for “research” purposes. Today, he is in a mall and would like to stare at people like usual. The mall is modelled as a grid and there are $N$ people, standing at locations $(x_ i, y_ i)$ that Lord Pooty wants to observe. There are also $K$ seats at locations $(x_ i,y_ i)$ that Lord Pooty can sit at to do his observation. Due to the inherent randomness of the universe that none can control, all the locations of people and seats are random.
He want to choose a seat where the maximum distance1 from the seat to any one person is minimised, to allow him better observation. As his fellow research buddy, help him find such a seat! If more than one seat is optimal, give him the minimum $(x,y)$ pair (i.e. $x$ is minimised, followed by $y$)!
Input
The first line contains integers $N$. ($1 \leq N \leq 200\, 000$). This is followed by $N$ lines of the following form: $x~ y$ ($-10^9 \leq x,y \leq 10^9$). These are the locations of the people. Then, you have an integer $K$. ($1 \leq K \leq 200\, 000$). This is followed by $K$ lines of the following form: $x~ y$ ($-10^9 \leq x,y \leq 10^9$). These are the locations of the seats.
All location inputs (people and seats) $(x, y)$ are UNIFORMLY, INDEPENDENTLY, RANDOMLY GENERATED integers from the range $[-10^9, 10^9]$. Note that it is possible for multiple inputs (seats and people) to be in the same location.
Output
Print $x$ and $y$, the location of the optimal seat. If more than one seat is optimal, print the minimum one.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 10 0 0 0 3 1 0 5 1 5 -1 |
5 -1 |
Footnotes
- Similar to the non-relativistic
classical model of our Universe, this problem is set in a
Euclidean space but of dimension $2$. Recall that Euclidean metric
$d$ is defined as:
d
Rn ×Rn ↦R
(x, y) ↦∑i = 1n (xi - yi)2
