Problem D
Gathering
In order to draw more support and make their unhappiness known to the municipality, a group of citizens has agreed to gather at an intersection of the city to protest. The question is: which intersection? Since there is not much difference between them, the idea was raised to select an intersection $(x^*,y^*)$ that minimizes the total distance everyone has to travel. Since everyone lives close to an intersection, the individual distance travelled by someone who lives at $(x,y)$ is given by $|x-x^*|+|y-y^*|$.
However, this could present a problem for the people who live far away, since they might have trouble getting there in time. Therefore it was decided that the intersection should be at most a certain distance $d$ away from everyone. Given that restriction, can you help them identify an intersection that minimizes the total distance everyone has to travel?
Input
The input consists of:
-
one line with one integer $n$ ($2 \leq n \leq 100\, 000$), the number of citizens;
-
$n$ lines each with two integers $x$ and $y$ ($0 \leq x,y \leq 10^9$), the coordinates of each citizen’s house;
-
one line with one integer $d$ ($0 \leq d \leq 2 \cdot 10^9$), the maximum distance that each citizen should have to travel.
It is possible for multiple citizens to live at the same intersection.
Output
Output one line with a single integer: the smallest possible total distance that all citizens need to travel. If there is no intersection that everyone lives within a distance $d$ of, output “impossible” instead.
Sample Input 1 | Sample Output 1 |
---|---|
5 3 1 4 1 5 9 2 6 5 3 10 |
18 |
Sample Input 2 | Sample Output 2 |
---|---|
5 3 1 4 1 5 9 2 6 5 3 5 |
20 |
Sample Input 3 | Sample Output 3 |
---|---|
5 3 1 4 1 5 9 2 6 5 3 4 |
impossible |