Description

In the 2D Cartesian coordinate system, there is a rectangle whose bottom-left corner is at $(0, 0)$ and top-right corner is at $(w, h)$, with its sides parallel to the coordinate axes.

Inside the rectangle, there are $n$ given points. The coordinates of the $i$-th point are $(x_i, y_i)$.

Please find a point inside the rectangle such that its distance to the nearest given point is as large as possible. You only need to output the value of this distance.

Input Format

The first line contains three integers $w, h, n$.

The next $n$ lines each contain two integers $x_i, y_i$.

Output Format

Output one real number in a single line, representing the maximum possible value of the nearest distance.

Your answer will be considered correct if its absolute error or relative error is within $10^{-6}$ of the standard output.

100 100 4
10 10
10 90
90 10
90 90

56.5685424949

3000 3000 4
1200 85
63 2500
2700 2650
2990 100

1601.8805541731

Hint

Sample Explanation 1

The required point is at $(50, 50)$, and its distance to the nearest given point is $40 \sqrt{2} \approx 56.568542494923802$.

Constraints

• For $50\%$ of the testdata, $n \le 50$.
• For $100\%$ of the testdata, $1 \le w, h \le 10\ 000$, $3 \le n \le 1000$, $0 \le x_i \le w$, $0 \le y_i \le h$.

The input may contain duplicate points.

Source: IOI 2006 CTT paper, "Wang Dong — A Brief Analysis of the Construction and Applications of Planar Voronoi Diagrams".

Translated by ChatGPT 5