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 图的构造及应用」。