Woburn Challenge 2002

Problem 6: Obstacles Galore

Cow-Bot has been successfully recovered! Bo Vine is very happy that he was able to retrieve his main spy, for now he can view all of the information that Cow-Bot gathered through his reconnaissance. Bo learns that the monkeys are still huddled in the middle of Scarberia, clumped tightly together, as would be expected of any friendly group, tending to their wounds. He wishes to seize this moment and attack while he has all the monkeys located near each other. To this end, he has invented A field Proven to Engulf (APE) its victims. Bo's plans are to deploy Cow-Bot, armed with an APE. The APE, once activated, will create a circular field emanating from the centre of the group of monkeys, radiating outwards with its radius growing at a fixed rate. Now, the APE is so strong, that no monkey can penetrate it and escape once it engulfs the monkey. However, if the growing APE comes into contact with an obstacle other than a monkey, it malfunctions and is destroyed! Note that once it attains a size large enough to engulf the monkeys, it stops growing.

Input

The first line of input contains a single integer, T (1 ≤ T ≤ 50), indicating the number of test cases.
Each test case begins with N, the number of obstacles (0 ≤ N ≤ 10000).
On the next N lines, the X-Y coordinates of each obstacle numbered 1→N (Real number)
On the next line, the X-Y coordinates of the center of the APE (Real number)
On the next line, the growth rate of the APE (units/second) (Real number)
On the next line, the radius of the APE when it engulfs the monkeys (and stops growing…)

Output

For each test case, output the following items (Round real numbers to 3 decimal places!)
  1. The time it takes for the APE to hit the first obstacle.
  2. The number of the obstacle that it hits (If more than one obstacle is hit simultaneously, output all)
  3. The radius of the APE at this time
OR, if the APE never hits an obstacle, output "The monkeys need help!"
Note that each of these numbers should occupy a separate line, except if the balloon encounters more than one obstacle in which case the obstacle numbers should appear in ascending order all on one line.
Leave a blank line between test cases.

Sample Input

3
3
1 1
-1 2.5
1 2
0 0
2
6
1
0 0
100 -100.124
11.2
124
4
1 1
-1 2.5
-1 1
1 -1
0 0
2
6

Sample Output

0.707
1
1.414

The monkeys need help!

0.707
1 3 4
1.414

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...