Самая далёкая пара
Даны точки на плоскости. Найдите две, между которыми расстояние наибольшее, и выведите квадрат этого расстояния — для целых координат это целое число. Точек до двухсот тысяч, так что перебрать все пары не получится. Один из тестов — все землетрясения силой от пяти баллов за 2015–2025 годы (каталог USGS, координаты в сотых долях градуса).
Вход
В первой строке n (1 ≤ n ≤ 200 000), дальше n строк с целыми x, y (|x|, |y| ≤ 10⁹). Точки могут совпадать.
Выход
Наибольший квадрат расстояния между двумя точками (0, если точка одна или все совпадают).
Примеры
Пример 1
5 0 0 4 0 4 3 0 3 2 1
25
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Может ли одна из двух самых далёких точек лежать строго внутри выпуклой оболочки?
2Подсказка 2
Вершин на оболочке бывает много — в шестом тесте шестьдесят тысяч. Для каждой стороны оболочки найдите вершину, самую далёкую от прямой этой стороны. Как меняется эта вершина, когда сторона сдвигается на одну дальше?
3Идея
Самая далёкая пара — две вершины оболочки: если точка внутри, отодвинуть её в сторону от второй точки можно, не выходя из оболочки, и расстояние вырастет. Перебирать пары вершин всё ещё дорого, но помогают вращающиеся калиперы: идём по сторонам оболочки по порядку и держим указатель на вершину, самую далёкую от текущей стороны. При переходе к следующей стороне этот указатель только сдвигается вперёд — это два указателя по кругу.
4Разбор
Строим оболочку монотонной цепочкой. Если вершин одна или две — ответ очевиден. Иначе для каждой стороны (a, b) двигаем j вперёд, пока площадь треугольника (a, b, hj+1) больше площади (a, b, hj) — то есть пока следующая вершина дальше от прямой ab. Площадь сравниваем векторным произведением, без деления. Кандидаты на ответ — пары (a, hj) и (b, hj).
Почему указатель обходит круг всего один раз: для выпуклого многоугольника расстояние от вершин до прямой стороны сначала растёт, потом убывает, и максимум при повороте стороны движется в ту же сторону. Всего i делает h шагов и j — не больше 2h.
4+Решение
5Сложность
O(n log n) на оболочку и O(h) на калиперы. Квадрат расстояния не больше 2·(2·10⁹)² = 8·10¹⁸ — помещается в int64.
6Типичные ошибки
- Перебор пар вершин оболочки. Для случайных точек оболочка маленькая, и перебор проходит. Но шестой тест — точки на параболе, и все шестьдесят тысяч — вершины.
- Корень из квадрата. Выводить нужно квадрат расстояния: так ответ точный.
- Остановка калиперов по «≥». Если двигать указатель при равных площадях, на параллельных сторонах он может уйти по кругу лишний раз. Строгое «>» безопасно.
Алгоритмы задачи
O(n log n)
2 задачи
GEO
Приём
Вращающиеся калиперы
У 971 из 2679 кварталов центра Алматы наименьший прямоугольник повёрнут на 4–8°: сетка улиц смотрит не строго на север.
O(n) после оболочки, O(n log n) с ней
2 задачи