Задачка

[Amph]

Это задачка из всемирного конкурса по программированию 2001 года.

На английском, естественно

Run Away
There are some traps in the Pharaoh's Pyramid, 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 scientists 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 Specification
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 Ui and Vi 0<=Ui<=X, 0<=Vi<=Y indicating the coordinates of one hole. There may be several holes at the same position.

Output Specification
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).

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

Output for the Sample Input

The safest point is (1000.0, 50.0).
The safest point is (50.0, 50.0).
The safest point is (1433.0, 1669.8).
------------------

Вот и всё. Есть мысли? Она только кажется простой на первый взгляд... а попробуйте найти оптимальное решение....

[Tumanyan]

Mysli takie:
Zadacha razdelyaetsya na 2 podzadachi:
1. Poisk maksimal'no udalennoj tochki po osi x.
2. Poisk maksimal'no udalennoj tochki po osi y.
T.e. na reshenie dvux podobnyx zadach, no s toj raznicej, chto kajdaya iz nix na odnomernom prostranstve.
Kajdaya iz podzadach opisyvaetsya grafikom:

0----x1-------x2.....-xn---xmax
0----y1-------y2.....-yn---ymax

Analiziruya grafik, prixodim k vyvodu, chto iskomaya tochka x naxoditsya posredi samogo dlinnogo otrezka iz mnojestva {0-x1, x1-x2....xn-xmax).

T.e. algoritm poluchaetsya takoj:
1. Podschitat' dliny vsex par iz mnojestva i zapisat' v massiv.
2. Najti naibol'shee znachenie v massive dlin.
3. Esli eto 0-x1 -> vzyat' 0 za iskomuyu tochku, esli xn-xmax - xmax - iskomaya tochka, v protivnom sluchae xmax = xi +(xi - xj) / 2.

To je samoe nado povtorit' dlya znacheniya y.

Vot i vse reshenie. Nu kak, optimal'no?