Hide

Problem G
Escape Plan

You are a land surveyor, and you use the latest land-surveying technology: robotic surveyors. You have sent your robots to survey a remote field, since it is cheaper and easier to send them than to go yourself. You know that there are frequent sand storms that blow through the field, which can damage the robots. Fortunately, satellite imagery can detect these storms and give the robots a warning several seconds before a storm arrives.

Since the field is so exposed and remote, the only way a robot can protect itself is to run to a hole in the ground and hide. You have identified the locations of several of these holes, but each of them is large enough to fit only one robot. Any robot that doesn’t make it into a hole before the storm arrives will be damaged.

Write a program that will figure out how many robots can escape a coming storm by running to and hiding in holes. Assume that each robot that can escape travels from its current position directly to a hole. All robots travel at a speed of 10 meters per second.

Input

The input will have multiple scenarios, at most $10$. Each scenario starts with an integer $0 < m \leq 200$ indicating the number of robots in the field, followed by $m$ lines indicating the $x$ and $y$ coordinates of each robot. Next comes an integer $0<n\leq 200$ indicating the number of holes, followed by $n$ lines indicating the $x$ and $y$ coordinates of each hole. All coordinates will be floating-point numbers, given in meters. No two holes will be at the same location, and no two robots will be at the same location. The end of input is signified by $m=0$.

Output

For each scenario, print the scenario number, and print how many robots could escape in 5 seconds, in 10 seconds, and in 20 seconds. Follow the format demonstrated in the sample output below. Print a blank line after each scenario. You may assume that the answers will not change if the threshold times (5, 10, or 20 seconds) are perturbed by up to $10^{-6}$ seconds.

Sample Input 1 Sample Output 1
3
0.0 0.0
10.0 0.0
0.0 10.0
3
99.0 0.0
0.0 1000.0
1000.0 1000.0
3
0.0 0.0
100.0 0.0
200.0 0.0
2
95.0 50.0
105.0 50.0
0
Scenario 1
In 5 seconds 0 robot(s) can escape
In 10 seconds 1 robot(s) can escape
In 20 seconds 1 robot(s) can escape

Scenario 2
In 5 seconds 0 robot(s) can escape
In 10 seconds 1 robot(s) can escape
In 20 seconds 2 robot(s) can escape

Please log in to submit a solution to this problem

Log in