March 28 ADA University Students + Schoolchildren
Безопасное расстояние
Прошлый год был трудным, вирус распространился среди населения. К счастью, Алиса знает, что один из ключей к здоровью - держаться на безопасном расстоянии от других людей.
Алиса в настоящее время находится в закрытой комнате, представленной в 2D-плоскости, шириной x и высотой y. В комнате есть n человек, и нам известны их координаты (x[i], y[i]).
Будем рассматривать Алису и этих n людей как точки в 2D плоскости. Начальное положение Алисы (0, 0), и она хочет перейти к выходу в позиции (x, y). Она может свободно перемещаться в любом направлении внутри комнаты, но не может выходить за пределы комнаты.
Найдите максимальное расстояние, на котором Алиса может держаться от других людей при перемещении от (0, 0) до (x, y).
Giriş verilənləri
Вход начинается с одной строки, содержащей два целых числа 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-го человека в комнате.
Çıxış verilənləri
Выведите одно действительное число d - максимальное безопасное расстояние. Допускается аддитивная или мультипликативная ошибка 10^(-5).
Nümunə
8 6 3 3 1 3 5.5 6.5 1.5
2.250000
Qeyd
Алиса может держаться на расстоянии 2,25 от любого другого человека, и это лучшее, на что она способна. На картинке ниже показан возможный путь (зеленым цветом).
