Defense of the Ancients

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3099
64-bit integer IO format: %I64d      Java class name: Main
Special Judge

Description

DotA? I’m afraid you’ve got a wrong impression, because we are talking about some real Ancients.
A lot of towers are in the first quadrant of rectangular coordinates. And between every two towers there is a wall. All of them are Ancients. Somehow, some skytroopers are trying to attack our Ancients and all we know is that they’ll land at the second, third and fourth quadrant of rectangular coordinates. Because those areas are desolation, the troops decided to follow a fixed straight line. Now we’ve got all the landing coordinates of the troops and the polar angle of their walking lines. To protect our Ancients, we need to know where the troops will first arrive at the Ancients.

Input

There are multiple test cases.
First line contains a single integer T (T<=10), indicates the number of test cases.
For each test case:
The first line has two positive integers N and M (1<N<=100000, M<=100000), represent the number of towers and skytroopers.
Following N lines, each line contains two integers X and Y, represents the coordinate of the tower.
Following M lines, each line has three integers SX, SY and XITA, indicates the coordinates of a skytrooper and the polar angle of their attacking line (in degrees). SX and SY will not bigger than 0 at the same time.
All the coordinates values lies in [-20000, 20000]. No two towers will be in same place.

Output

For every skytrooper, output one line, if the trooper can reach the Ancients, output the coordinate he will first arrive, otherwise output “safe”.
If the value differs in 0.01 with our standard output, we’ll consider it as accepted.

Sample Input

1
6 3
5 1
8 5
13 2
14 7
7 9
1 7
-2 -2 45
8 -2 90
-3 7 120

Sample Output

3.400000 3.400000
8.000000 1.375000
safe

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .