Сколько треугольников
Геодезисты разбивают местность на треугольники с вершинами в точках съёмки — так строят модель рельефа. Как именно провести треугольники, решает программа, но сколько их получится, можно сказать заранее, ничего не строя.
Даны n различных точек плоскости, не лежащих все на одной прямой. Триангуляция — разбиение их выпуклой оболочки на треугольники с вершинами в данных точках: треугольники не перекрываются, вместе покрывают оболочку, и ни одна данная точка не лежит внутри треугольника или на его стороне, кроме как в вершине. Сколько в триангуляции треугольников и сколько рёбер?
Второй пример — 17 пожарных частей Алматы; в тестах есть 7909 перекрёстков улиц города и 45 209 городов мира (долгота и широта в тысячных долях градуса, совпадающие точки убраны).
Вход
В первой строке n (3 ≤ n ≤ 105). Дальше n строк — целые координаты x и y точек (|x|, |y| ≤ 109). Все точки различны и не лежат на одной прямой.
Выход
Два числа: сколько треугольников и сколько рёбер в триангуляции.
Примеры
Пример 1
6 0 0 4 0 4 4 0 4 1 2 2 0
5 10
Пример 2
17 -1103 -2324 956 2247 1087 2866 -4952 1175 3977 8694 19202 11873 11803 -9089 -5390 -526 6689 12570 -8604 -6793 -6811 771 5915 5067 -1000 6934 -555 10065 -3493 -4205 -6305 8196 3386 603
27 43
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Нарисуйте несколько маленьких примеров. Три точки — один треугольник и три ребра. Квадрат — два треугольника и пять рёбер. Квадрат с точкой внутри — четыре и восемь. Что меняет точка внутри, а что — точка на границе?
2Подсказка 2
Триангуляция — плоский граф, а для плоского графа есть формула Эйлера: вершины минус рёбра плюс грани равно двум. Вторую связь между числами даёт подсчёт сторон граней: у треугольника три стороны, у внешней грани — сколько точек на границе оболочки.
3Подсказка 3
Ответ зависит только от n и от числа h точек на границе выпуклой оболочки. Считаются не только её углы, но и точки, лежащие на её сторонах: каждая из них — вершина внешней грани. Как найти оболочку, не потеряв такие точки?
4Идея
Пусть T треугольников, E рёбер, и граней T + 1 — треугольники и внешняя. По формуле Эйлера n − E + T + 1 = 2. Каждое ребро — сторона ровно двух граней, а сторон у треугольников 3T, у внешней грани — h: 3T + h = 2E. Из двух равенств T = 2n − 2 − h и E = 3n − 3 − h. Доказательство целиком — в статье. Ответ один для любой триангуляции: Делоне, веера, любой другой.
5Разбор
Остаётся найти h. Монотонная цепь: точки сортируются по x, потом по y; нижняя цепь идёт слева направо и выбрасывает последнюю точку, пока поворот вправо, верхняя — справа налево. Выбрасывать нужно только при строгом повороте вправо, а на прямом участке точку оставлять — тогда точки на сторонах оболочки остаются в цепях. h — сумма длин цепей без повторённых концов.
Первый пример: квадрат 4 × 4, точка (2, 0) в середине нижней стороны и точка (1, 2) внутри. На границе пять точек, h = 5: треугольников 2·6 − 2 − 5 = 5, рёбер 3·6 − 3 − 5 = 10. У частей Алматы на оболочке пять точек из 17 — 27 треугольников и 43 ребра, у сетки 250 × 250 на границе 996 точек.
5+Решение
6Сложность
Сортировка — O(n log n), цепи — O(n): каждая точка входит и выходит не больше одного раза. Строить саму триангуляцию не нужно; если всё-таки строить, даже лучшие алгоритмы — тоже O(n log n), только с большим множителем.
7Типичные ошибки
- Только углы оболочки. Цепь, которая выбрасывает точку и на прямом участке, теряет точки на сторонах. Ответ ошибается уже на первом примере, а на сетке — на тысячу.
- Только вершины, без внутренних точек. Точки внутри тоже вершины триангуляции: каждая добавляет два треугольника и три ребра.
- Переполнение. Векторное произведение при координатах до 109 — до 8·1018: в 64-битное число со знаком оно помещается, в 32-битное и в double без потери точности — нет.