P1379. 逃离

问题描述

在金字塔中，我们将遇到的一个陷阱位于大厅。地板上钻有许多小孔。乍一看，它们看起来完全无害。但一旦被激活，它们会开始喷出非常热的咖啡，呃……抱歉，是熔岩。不幸的是，所有通往中心大厅（放置石棺的地方）的已知路径都包含一个触发陷阱的触发器。ACM 无法避免这一点。但他们仔细监测了所有孔的位置。因此，找到大厅中距离所有孔最远的地方非常重要。这个地方是整个房间中最安全的，考古学家必须躲在那里。

输入

输入包含 T 个测试用例。输入文件的第一行给出测试用例的数量 T。每个测试用例以一行开始，包含三个整数 X、Y 和 M，以空格分隔。这些数字满足条件：$$1 ≤ X, Y ≤ 10000，1 ≤ M ≤ 1000$$。$X$ 和 $Y$ 表示大厅的尺寸，呈矩形。$M$ 表示孔的数量。接下来是 $M$ 行，每行包含两个整数 $Ui$ 和 $$Vi（0 ≤ Ui ≤ X，0 ≤ Vi ≤ Y）$$，表示一个孔的坐标。可能会有多个孔位于同一位置。

输出

对于每个测试用例，输出一行。该行应包含句子 $$"The safest point is (P, Q)."$$，其中 $P$ 和 $Q$ 是房间中距离最近孔最远的点的坐标，四舍五入到小数点后一位（$0.05$ 向上取整为 $0.1$）。

输入示例 1

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

输出示例 1

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

来源

Central Europe 1999

如果需要进一步帮助，请告诉我！