Задача №114678. Прибытие
НЛО будет посажен так, что все точки на его границе окажутся строго внутри ограничивающего прямоугольника. Ученых интересует максимальный радиус НЛО \(r\) такой, что можно посадить корабль, не повредив ни одной ёлки. Ёлка считается поврежденной, если она оказалась строго внутри одной из окружностей, составляющих корабль.
В первой строке вводится \(t\) (\(1 \le t \le 1000\)) — количество наборов входных данных. В следующих строках содержатся описания каждого тестового набора.
В первой строке каждого описания вводятся два целых числа \(x, y\) (\(2 \le x, y \le 10\,000\)) — размеры ограничивающего прямоугольника.
Во второй строке вводится одно целое число \(n\) (\(1 \le n \le 1000\)) — количество ёлок.
В следующих \(n\) строках вводятся по два целых числа \(x_i, y_i\) (\(1 \le x_i \le x - 1, 1 \le y_i \le y - 1\)) — координаты ёлок.
Гарантируется, что координаты всех ёлок различны в каждом из наборов входных данных.
Для каждого тестового набора выведите вещественное число \(r\) — максимальный радиус НЛО с абсолютной или относительной погрешностью не более \(10^{-6}\).
Тесты к этой задаче состоят из 9 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Обозначим за \(N\) сумму \(n_i\) по всем тестовым набором внутри одного теста.
| Доп. ограничения | |||||
| Группа | Баллы | \(n_i\) | \(N\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 4 | \(n_i = 1\) | \(N \le 10\) | – | |
| 2 | 7 | \(n_i \le 2\) | \(N \le 10\) | 1 | |
| 3 | 18 | \(n_i \le 10\) | \(N \le 10\) | 0 – 2 | |
| 4 | 13 | \(n_i \le 30\) | \(N \le 30\) | 0 – 3 | |
| 5 | 10 | \(n_i \le 50\) | \(N \le 50\) | 0 – 4 | |
| 6 | 6 | \(n_i \le 100\) | \(N \le 100\) | 0 – 5 | |
| 7 | 8 | \(n_i \le 300\) | \(N \le 300\) | 0 – 6 | |
| 8 | 14 | \(n_i \le 500\) | \(N \le 500\) | 0 – 7 | |
| 9 | 20 | \(n_i \le 1000\) | \(N \le 1000\) | 0 – 8 | Offline-проверка. |
4 5 3 1 2 2 5 5 3 3 2 2 3 4 4 5 10 4 3 8 2 2 3 3 4 4 4 2 1 2 1
1.17157287430693495846 1.17851130088000507091 1.62701665365602821112 0.99999999906867742538
1 10 10 10 1 4 2 7 3 2 5 8 6 1 6 2 6 7 7 2 7 8 8 5
1.96492223990317443558
1 1505 1671 10 38 912 147 740 149 266 259 459 360 802 513 523 692 299 717 1185 1114 362 1363 1536
368.18025897753007949498