Задача №114697. Футболки на олимпиаду
Наконец-то пришло время для финала Закрытой олимпиады школьников по программированию! Все отборы пройдены, сувенирные футболки лежат в пакетах. Вот только распределение участников по площадкам еще не спланировано.
У жюри олимпиады есть \(m\) площадок проведения. На \(i\)-й площадке лежит пакет, в котором находится \(a_i\) футболок. Это значит, что на эту площадку можно зарегистрировать не более \(a_i\) участников. Всего же среди финалистов будет \(n\) человек.
Финал Закрытой олимпиады школьников по программированию проходит в городе-герое Кленинграде. Как любой другой город Флатландии, он расположен в декартовой системе координат. Жюри знает адрес каждого финалиста — координаты \(X_i,\,Y_i\), а также адреса площадок — координаты \(x_i,\,y_i\).
Жюри хочет так распределить участников по точкам проведения, чтобы всем участникам хватило футболок, при этом максимальное из расстояний, которое придется пройти участнику до точки проведения, было как можно меньше. Поскольку жюри олимпиады сейчас везет на точки проведения другую сувенирку, Вас попросили провести распределение участников по площадкам.
В первой строке заданы два целых числа \(n\), \(m\) (\(1 \le n,\, m \le 500\)) — количество участников олимпиады и точек проведения.
В следующих \(n\) строках заданы пары целых чисел \(x_i,\,y_i\) (\(1 \le x_i,\,y_i \le 10^6\)) — координаты \(i\)-го участника олимпиады.
В следующих \(m\) строках заданы тройки целых положительных чисел \(X_i,\,Y_i,\,a_i\) (\(1 \le X_i,\,Y_i \le 10^6\), \(1 \le a_i \le n\)) — координаты \(i\)-й площадки и ее вместимость.
Гарантируется, что сумма \(a_i\) не меньше \(n\), а так же что она не превосходит \(1000\).
Выведите одно число — максимальное расстояние, которое придется пройти участнику до точки проведения олимпиады при оптимальном распределении. Ответ будет считаться верным, если его абсолютная или относительная ошибка не будет превосходить \(10^{-6}\). Формально, пусть ваш ответ равен \(a\), а ответ жюри — \(b\). Ваш ответ считается правильным, если \(\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}\).
В первом примере надо отправить первого участника на первую площадку, а оставшихся двух — на вторую. Тогда первый участник пройдет расстояние 0, а второй и третий — по 1.
Во втором примере надо первого и второго участников отправить на площадку \(1\), а третьего — на площадку \(2\). Тогда первый участник пройдёт расстояние \(1.41421356237\), второй — \(0\), а третий — \(4.2426406871\).
Тесты к этой задаче состоят из девяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(m\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 10 | – | – | \(a_i = n\) | – | |
| 2 | 11 | – | \(m \le 2\) | – | 0 | |
| 3 | 15 | – | \(m \le 3\) | – | 0, 2 | |
| 4 | 14 | \(n \le 10\) | \(m \le 10\) | – | 0 | |
| 5 | 13 | \(n \le 50\) | \(m \le 50\) | – | 0, 4 | |
| 6 | 7 | \(n \le 200\) | \(m \le 200\) | – | 0, 4, 5 | |
| 7 | 9 | \(n \le 300\) | \(m \le 300\) | – | 0, 4, 5, 6 | |
| 8 | 10 | \(n \le 400\) | \(m \le 400\) | – | 0, 4, 5, 6, 7 | Offline-проверка. |
| 9 | 11 | – | – | – | 0–8 | Offline-проверка. |
3 2 1 1 2 3 3 2 1 1 1 2 2 2
1.0000000000
3 2 100 100 101 101 102 102 101 101 2 105 105 2
4.2426406871