Czech Technical University in Prague
ICPC Foundation
Czech ACM Chapter
Central Europe Regional Contest 2019
Deep800080
deep.c, deep.cpp, Deep.java, deep.py
Ian, the owner of the boat called Deep800080 is going to make a barbecue on the lake this
evening. There is a narrow straight pier running from the shore into the lake. Ian thinks it will
be a good idea to make the barbecue somewhere on the pier.
He wants to test his new special barbecue charcoal. When it burns it produces a distinctive
thick purple smoke which spreads over the water. The cloud of smoke is guaranteed to spread
in a perfect circle around the barbecue site. Eventually, the cloud will reach some maximum
radius and will stay unchanged for the rest of the evening until it dissipates later in the night.
There are multiple boats anchored in the lake in various distances from the pier. Ian wants to
inform their crews about the barbecue. Being a little lazy, he hopes that the barbecue smoke
will do this job for him. Ian hopes that when the cloud reaches a boat, the crew can smell the
smoke, and so they immediately know there is a barbecue nearby.
Ian wants to maximize the number of alerted crews and thus he wants to choose a place of the
barbecue grill on the pier which would maximize the number of the boats reached by the purple
cloud.
You may assume that the boats on the lake are firmly anchored and that they do not move
while the cloud is on the lake. Also, once the barbecue site is chosen, its position remains fixed
for the whole event.
Input Specification
The first line contains four integers N, R, A, B (0 ≤ N ≤ 3 · 105; 1 ≤ R ≤ 106). N is the number
of boats on the lake, R is the maximal radius of the purple barbecue cloud. You may assume
that the pier is so narrow and so long that it may be perceived as a straight line passing through
two distinct points with coordinates (0, 0) and (A, B).
Each of the next N lines contains two integers X and Y describing the coordinates of one boat
on the lake. No two boats share the same coordinates.
All coordinates are common Cartesian coordinates in the plane, their absolute value will be at
most 106.
Output Specification
Output the maximum possible number of boats that can be reached by the purple barbecue
cloud.
A boat is considered reached if its position is in the circle formed by the cloud, including its
boundary. You may assume that increasing the maximal radius of the smoke cloud by 10-3
would not change the solution.
Output for Sample Input 1
Sample Input 1
5
7501
-1 -1
1 -1
00
23
34
10 10
2 12
Sample Input 2
Output for Sample Input 2
3
110
2
0
0
2
0
4
0
Sample Input 3
Output for Sample Input 3
4
110
4
0
0
1
1
1
-1
2
0
1
12
1
2
3
4
-1
10
8
-1
6
4
1
2
2
4
6
8
10
12
-4
-2
-2
1
2
3
-1
-4
-1
Figure 1: Possible solution of Sample Input 1 (left), Sample Input 2 (top right) and Sample
Input 3 (bottom right)
