Где поставить новую часть
В городе стоят пожарные части. Городу нужна новая, и поставить её хотят там, где сейчас до ближайшей части дальше всего. Выбирают внутри одного района — многоугольника; части могут стоять и за его пределами. Расстояние считается по прямой.
Найдите наибольшее по всем точкам района, внутри и на границе, расстояние до ближайшей части.
В тестах — восемь районов Алматы и 17 пожарных частей, отмеченных в OpenStreetMap, в метрах; у района, состоящего из двух кусков, взят больший.
Вход
В первой строке n и m (1 ≤ n ≤ 300, 3 ≤ m ≤ 3000) — число частей и вершин района. Дальше n строк — целые координаты частей, все различны, и m строк — вершины района по порядку обхода. Многоугольник простой: стороны не пересекаются. Все координаты по модулю не больше 106.
Выход
Одно число — наибольшее расстояние. Ответ принимается с относительной ошибкой до 10−6.
Примеры
Пример 1
2 4 2 5 8 5 0 0 10 0 10 10 0 10
5.830952
Пример 2
3 3 1 1 10 1 3 12 0 0 12 0 0 9
5.948297
Ограничения
- Время · Python
- 16000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 14 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Расстояние до ближайшей части как функция точки устроено просто внутри одной зоны Вороного: там ближайшая — одна и та же часть, и расстояние растёт по мере удаления от неё. Где тогда может быть максимум?
2Подсказка 2
Внутри района максимум может быть только там, где точку нельзя отодвинуть от всех ближайших частей сразу, — в вершине Вороного, равноудалённой от трёх частей. На границе района — в вершине многоугольника или там, где сторона переходит из одной зоны в другую.
3Подсказка 3
Первый пример: квадрат и две части на одной высоте. Углы квадрата дают 5,39, а середины нижней и верхней сторон, где сторона переходит из зоны одной части в зону другой, — 5,83. Как найти такие точки на каждой стороне, не перебирая все пары частей?
4Идея
Пусть точка x района — не вершина Вороного и не точка границы. Если у неё одна ближайшая часть p, сдвинем x немного от p: расстояние до p вырастет, а ближайшей останется p. Если ближайших две, p и q, x лежит на их серединном перпендикуляре, и по нему можно сдвинуться от обеих сразу. Так что максимум — в вершине Вороного внутри района или на границе. На стороне многоугольника работает то же рассуждение, только сдвигаться можно лишь вдоль стороны: максимум — в её конце или там, где меняется ближайшая часть.
5Разбор
Вершины Вороного. Ячейка части i — пересечение полуплоскостей «ближе к i, чем к j» по всем j; обрежем ими прямоугольник вокруг района, и вершины получившегося многоугольника — вершины Вороного (или точки на краю прямоугольника, они вне района). Значение в вершине ячейки i — расстояние до i: она одна из ближайших. Отсортируем вершины по убыванию значения и проверим, лежит ли внутри района, только первые, пока значение больше уже найденного ответа, — первая же внутренняя заканчивает поиск. Быстрее — через триангуляцию Делоне: вершины Вороного — центры описанных окружностей её треугольников.
Граница. На стороне ab начнём с ближайшей к a части s и параметра t = 0. Точка a + t(b − a) становится ближе к части j, чем к s, после пересечения их серединного перпендикуляра, и это пересечение — решение линейного уравнения по t. Берём наименьшее t больше текущего среди частей, к которым мы движемся, переходим в него и меняем s. Каждая такая точка и конец стороны — кандидат, а значение в нём — расстояние до текущей s.
У районов Алматы ответы — от 3 км в Ауэзовском и Алмалинском районах до 16,7 км в Бостандыкском: там граница уходит в горы.
5+Решение
6Сложность
Ячейки — O(n2) отсечений, каждое — по числу вершин ячейки (в среднем их около шести). Обход границы — O(m · n) плюс по O(n) на каждую смену зоны. Проверка «внутри района» — O(m), но её почти не приходится делать. С триангуляцией Делоне вершины Вороного находятся за O(n log n).
7Типичные ошибки
- Забыть границу. Только вершины Вороного и углы района: в первом примере 5,39 вместо 5,83.
- Все тройки частей. Центр окружности через любые три части — не обязательно вершина Вороного: внутри окружности может оказаться четвёртая часть. Перебор троек с проверкой пустоты верен, но это O(n4).
- Части вне района. Они влияют на расстояния внутри, и выбрасывать их нельзя: в тринадцатом тесте единственная часть далеко за пределами.
- Части на одной прямой. Вершин Вороного нет вовсе, серединные перпендикуляры параллельны — ответ целиком на границе.