Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2018
Security Guards
security.c, security.cpp, security.c11, Security.java, security.py
In the course of the last few weeks, Binary Casino has been afflicted by a local crime wave which
is primarily focused on casinos in the neighborhood. Although there are surveillance cameras
installed in Binary Casino, thieves usually manage to sneak out with relative ease as there is
almost nobody patrolling in the casino.
After the theft of all Friday's earnings, the manager of Binary Casino has lost his patience and
decided to reinforce security of the casino by hiring a vast number of security guards. However,
nobody in the casino was capable of coming up with a plan on how to distribute guards across
the whole casino to maximize security. Security guards are thus scaterred across the casino in
no systematic way. Fortunately, their locations can be described by integer coordinates in a 2D
plane.
Because of the uneven distribution of security guards, in case of a reported robbery it is very
hard for security supervisors to determine which guard is closest to the location of the incident.
The task is even harder due to the constrained space in the casino which consists of endless
aisles of slot machines. This limitation forces each guard to travel from one location to another
in a sequence of steps. In each step, he/she can change each of his/her coordinates by 1, 0 or
-1. The distance between two locations is equal to the minimum number of steps the guard has
to do to get from one location to the other one.
The task is, for a given locations of guards and a set of locations of security incidents, to compute
for each incident its smallest distance to any of the guards. This will allow security supervisors
to alert appropriate guards and will greatly increase the casino security.
Input Specification
The first line of input contains two integers N and Q (1 ≤ N, Q ≤ 3 · 105), the number of
guards and the number of security incidents, respectively. After that, N lines follow. Each of
these lines contains two integers X and Y (0 ≤ X, Y ≤ 5000) which describe 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 coordinates of a security incident.
Output Specification
For each of Q security incidents output a line containing shortest distance to any of the security
guards, measured in steps.
Output for Sample Input 1
Sample Input 1
1
2
3
3
0
1
1
4
0
5
0
4
3
1
2
Output for Sample Input 2
Sample Input 2
1
2
4
3
0
0
2
3
3
0
1
1
0
3
1
2
3
3
