P6505 Run Away
题目描述
平面直角坐标系内有一个矩形,左下角坐标为 $(0, 0)$,右上角为 $(w, h)$,边平行于坐标轴。
矩形内有 $n$ 个已知点,第 $i$ 个点坐标为 $(x_i, y_i)$。
请找到矩形内一点,使得这个点到最近的已知点距离最远。输出这个距离的值即可。
输入格式
第一行输入三个整数 $w, h, n$。
接下来 $n$ 行,每行输入两个整数 $x_i, y_i$。
输出格式
输出一行一个实数,表示最近距离的最大值。
当你的答案与标准输出的绝对误差或相对误差在 $10^{-6}$ 内时,就会被视为正确。
说明/提示
#### 样例解释 1
所求点坐标为 $(50, 50)$,到已知最近点的距离为 $40 \sqrt{2} \approx 56.568542494923802$。
---
#### 数据范围
- 对于 $50\%$ 的数据,$n \le 50$。
- 对于 $100\%$ 的数据,$1 \le w, h \le 10\ 000$,$3 \le n \le 1000$,$0 \le x_i \le w$,$0 \le y_i \le h$。
输入数据中可能有重点。
---
来源:IOI 2006 国家集训队论文「王栋 —— 浅析平面 voronoi 图的构造及应用」。