March 28 ADA University Students + Schoolchildren
Безопасное расстояние
Прошлый год был трудным, вирус распространился среди населения. К счастью, Алиса знает, что один из ключей к здоровью - держаться на безопасном расстоянии от других людей.
Алиса в настоящее время находится в закрытой комнате, представленной в 2D-плоскости, шириной x и высотой y. В комнате есть n человек, и нам известны их координаты (x[i]
, y[i]
).
Будем рассматривать Алису и этих n людей как точки в 2D плоскости. Начальное положение Алисы (0, 0), и она хочет перейти к выходу в позиции (x, y). Она может свободно перемещаться в любом направлении внутри комнаты, но не может выходить за пределы комнаты.
Найдите максимальное расстояние, на котором Алиса может держаться от других людей при перемещении от (0, 0) до (x, y).
Вхідні дані
Вход начинается с одной строки, содержащей два целых числа x и y (1 ≤ x, y ≤ 10^6
), где x - ширина, y - высота комнаты. Вторая строка содержит количество людей n (1 ≤ n ≤ 1000) в комнате. Каждая из следующих n строк состоит из двух действительных чисел x[i]
и y[i]
(0 ≤ x[i]
≤ x, 0 ≤ y[i]
≤ y) - координат i-го человека в комнате.
Вихідні дані
Выведите одно действительное число d - максимальное безопасное расстояние. Допускается аддитивная или мультипликативная ошибка 10^(-5)
.
Приклад
8 6 3 3 1 3 5.5 6.5 1.5
2.250000
Примітка
Алиса может держаться на расстоянии 2,25 от любого другого человека, и это лучшее, на что она способна. На картинке ниже показан возможный путь (зеленым цветом).
