Безпечна відстань#10724

Безпечна відстань

2 секунди

128 мегабайтів

Складна

Минулого року був важкий період, коли вірус поширився серед населення. На щастя, Аліса знає, що для збереження здоров'я важливо триматися на безпечній відстані від інших людей.

Аліса зараз перебуває в закритій кімнаті, яка представлена у вигляді 2D-площини з шириною $x$ і висотою $y$ . У цій кімнаті знаходяться $n$ людей, і ми знаємо їхні координати $(x_{i}, y_{i})$ (x_i, y_i).

Розглянемо Алісу та цих $n$ людей як точки на 2D площині. Початкове положення Аліси — $(0, 0)$ , і вона хоче дістатися до виходу, який знаходиться в точці $(x, y)$ . Вона може вільно переміщатися в будь-якому напрямку всередині кімнати, але не може виходити за її межі.

Знайдіть максимальну відстань, на якій Аліса може триматися від інших людей під час переміщення від $(0, 0)$ до $(x, y)$ .

Вхідні дані

Перший рядок містить два цілі числа $x$ і $y (1 \leq x, y \leq 1 0^{6})$ y~(1 \le x, y \le 10^6), де $x$ — ширина, а $y$ — висота кімнати. Другий рядок містить кількість людей $n (1 \leq n \leq 1000)$ n~(1 \le n \le 1000) у кімнаті. Кожен з наступних $n$ рядків містить два дійсних числа $x_{i}$ x_i і $y_{i} (0 \leq x_{i} \leq x, 0 \leq y_{i} \leq y)$ y_i~(0 \le x_i \le x, 0 \le y_i \le y) — координати $i$ -ї людини в кімнаті.

Вихідні дані

Виведіть одне дійсне число $d$ — максимальну безпечну відстань. Допускається адитивна або мультиплікативна похибка $1 0^{- 5}$ 10^{-5}.

Приклади

Аліса може триматися на відстані $2.25$ від будь-якої іншої людини, і це найкраще, що вона може зробити. На малюнку нижче показано можливий шлях (зеленим кольором).

Приклад 1