Security Guards
Time limit2sMemory limit512 MB
On an 8-connected grid with Chebyshev distance, given up to 3e5 guard points and 3e5 query points in [0,5000]^2, output for each query the distance to the nearest guard.
- Level
Medium7 of 10
- Topics
- BFS, Matrix, Implementation, Shortest path
- Solved
- No attempts yet
Problem
Over the past few weeks, Binary Casino has been hit by a local crime wave aimed mainly at casinos in the neighborhood. Surveillance cameras are installed in Binary Casino, but thieves usually slip away with ease because almost nobody patrols the casino.
After all of Friday's earnings were stolen, the manager of Binary Casino lost his patience and decided to reinforce the casino's security by hiring a large number of security guards. Nobody at the casino could come up with a plan to distribute guards across the whole casino so as to maximize security. The guards are therefore scattered around the casino with no systematic arrangement. Fortunately, their locations can be described by integer coordinates in a 2D plane.
Because the guards are unevenly distributed, when a robbery is reported the security supervisors have a very hard time determining which guard is closest to the scene. The task is even harder because the casino consists of endless aisles of slot machines. This forces each guard to travel from one location to another in a sequence of steps. In each step, a guard can change each of his or her coordinates by 1, 0, or -1. The distance between two locations equals the minimum number of steps a guard must take to get from one location to the other.
Given the locations of the guards and a set of locations of security incidents, the task is to compute, for each incident, its smallest distance to any guard. This lets the security supervisors alert the appropriate guards and greatly improves the casino's security.
Input
The first line of input contains two integers N and Q (1 ≤ N, Q ≤ 3 · 10^5), the number of guards and the number of security incidents. After that, N lines follow. Each of these lines contains two integers X and Y (0 ≤ X, Y ≤ 5000), which describe the coordinates of a guard in a 2D plane. Next, Q lines follow. Each of these lines contains two integers A and B (0 ≤ A, B ≤ 5000), which describe the coordinates of a security incident.
Output
For each of the Q security incidents, output one line containing the shortest distance to any security guard, measured in steps.