RUNAWAY  Run Away
One of the traps we will encounter in the Pyramid is located in the Large Room. A lot of small holes are drilled into the floor. They look completely harmless at the first sight. But when activated, they start to throw out very hot java, uh ... pardon, lava. Unfortunately, all known paths to the Center Room (where the Sarcophagus is) contain a trigger that activates the trap. The ACM were not able to avoid that. But they have carefully monitored the positions of all the holes. So it is important to find the place in the Large Room that has the maximal distance from all the holes. This place is the safest in the entire room and the archaeologist has to hide there.
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing three integers X, Y, M separated by space. The numbers satisfy conditions: 1 <= X,Y <=10000, 1 <= M <= 1000. The numbers X and Yindicate the dimensions of the Large Room which has a rectangular shape. The number M stands for the number of holes. Then exactly M lines follow, each containing two integer numbers U_{i} and V_{i} (0 <= U_{i} <= X, 0 <= V_{i} <= Y) indicating the coordinates of one hole. There may be several holes at the same position.
Output
Print exactly one line for each test case. The line should contain the
sentence "The safest point is (P, Q).
"
where P and Qare the coordinates of the point in the
room that has the maximum
distance from the nearest hole, rounded to the nearest number with exactly
one digit after the decimal point (0.05 rounds up to 0.1).
Example
Sample Input: 3 1000 50 1 10 10 100 100 4 10 10 10 90 90 10 90 90 3000 3000 4 1200 85 63 2500 2700 2650 2990 100 Sample output: The safest point is (1000.0, 50.0). The safest point is (50.0, 50.0). The safest point is (1433.0, 1669.8).
hide comments
pkuzby:
20181204 21:20:29
What should the output be if there are multiple points with equal maximal distance? Last edit: 20181204 21:20:55 

Sreekanth Pathi:
20140320 21:53:20
origin??


rafiki93:
20130313 12:56:54


Santiago Palacio:
20110608 15:34:57
0 <= Ui <= x ? the holes can be on the border? 

:
20101210 23:32:06
This is a "Largest Empty Circle" Problem. 

vignesh:
20100223 11:33:55
Can this problem be solved using a convex hull? 
Added by:  adrian 
Date:  20040606 
Time limit:  13s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  ACM Central European Programming Contest, Prague 1999 