Bus Terminal
Time limit5sMemory limit128 MB
Given N grid points, pick two hub points and assign every other point to one hub so that the maximum pairwise routing distance through the hubs is minimized.
- Level
Hard8 of 10
- Topics
- Greedy, Geometry, Binary search
- Solved
- No attempts yet
Problem
Yongin is planning a bus route using N bus stops placed on a square grid. Choose two of the stops as central stops H1 and H2. The two central stops are connected directly, and every other stop is connected directly to exactly one of H1 and H2.
The basic distance between two grid points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|. If two stops are connected to the same central stop, their route distance is the sum of their basic distances to that central stop. If they are connected to different central stops, their route distance is the distance from the first stop to its central stop, plus the distance between H1 and H2, plus the distance from the other central stop to the second stop.
Choose the two central stops and the connection for each remaining stop so that the largest route distance between any two stops is as small as possible. Compute that minimum possible value.
Input
The first line contains an integer N (2 <= N <= 500), the number of bus stops. Each of the next N lines contains two integers x and y, the coordinates of one stop. x is the horizontal coordinate and y is the vertical coordinate. Every coordinate is a positive integer not greater than 5000, and no two stops have the same position.
Output
Print one integer: the minimum possible value of the largest route distance between two stops.