Яблони в узлах сетки
Яблоневый сад засажен по линейке: деревья стоят во всех узлах квадратной сетки с шагом в одну единицу, то есть во всех точках с целыми координатами. Участок обнесён забором — многоугольником с вершинами в узлах сетки. Яблони, через которые проходит забор, придётся пересадить. Сколько деревьев растёт строго внутри участка и сколько стоит на заборе?
Координаты бывают до миллиарда, так что перебрать узлы не выйдет: в самом большом участке их около 4·10¹⁸. Третий тест — Ауэзовский район Алматы из OpenStreetMap, переведённый в целые метры на сетке карты дорог этого каталога: сколько узлов метровой сетки внутри района.
Вход
В первой строке число вершин n (3 ≤ n ≤ 100 000). Дальше n строк с целыми координатами вершин x y (|x|, |y| ≤ 10⁹) в порядке обхода — по часовой стрелке или против, как получится. Забор не пересекает и не касается сам себя: соседние стороны встречаются только в общей вершине, остальные не имеют общих точек. Вершины не повторяются, но три вершины подряд могут лежать на одной прямой.
Выход
Два целых числа через пробел: сколько узлов сетки лежит строго внутри многоугольника и сколько — на его границе, включая вершины.
Примеры
Пример 1
5 1 1 7 2 6 6 4 4 2 7
18 6
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Начните с забора. Сколько узлов сетки лежит на отрезке из (0, 0) в (6, 4)? А в (6, 5)? Найдите общее правило для отрезка с концами в узлах.
2Подсказка 2
Узлы внутри перебирать нельзя, но площадь многоугольника с вершинами в узлах считается точно — формулой шнурков, в целых числах. Площадь и число узлов связаны: на клетчатой бумаге у фигуры, где узлов внутри много, и площадь большая.
3Подсказка 3
Это формула Пика: для многоугольника с вершинами в узлах сетки S = I + B/2 − 1, где I — узлы внутри, B — узлы на границе. Проверьте её на квадрате 1 × 1 и на прямоугольном треугольнике с катетами 3 и 3.
4Идея
На стороне из (x₁, y₁) в (x₂, y₂) лежит gcd(|x₂ − x₁|, |y₂ − y₁|) + 1 узел, считая оба конца. Если у каждой стороны считать только конец, а начало оставить предыдущей, получится B = Σ gcd(|Δx|, |Δy|) без повторов. Удвоенная площадь 2S — модуль суммы шнурков, целое число. Из формулы Пика 2I = 2S − B + 2.
5Разбор
Узлы на стороне. Пусть Δx = x₂ − x₁, Δy = y₂ − y₁ и g = gcd(|Δx|, |Δy|). Точки (x₁ + kΔx/g, y₁ + kΔy/g) при k = 0, 1, …, g — узлы на стороне, их g + 1. Других нет: точка стороны — это (x₁ + tΔx, y₁ + tΔy) при 0 ≤ t ≤ 1, и если обе её координаты целые, то tΔx и tΔy — целые числа. Тогда целое и t·g: по соотношению Безу g = aΔx + bΔy для каких-то целых a и b, и tg = a·tΔx + b·tΔy. Значит, t = k/g. Наибольший общий делитель считается алгоритмом Евклида.
Площадь. 2S = |Σ (xiyi+1 − xi+1yi)|, индексы по кругу. Модуль нужен, потому что направление обхода любое.
Ответ. I = (2S − B + 2) / 2, деление нацело: по формуле Пика числитель всегда чётный. Почему формула Пика верна, разобрано в статье о площади многоугольника.
Про переполнение в Go. Удвоенная площадь участка в квадрате со стороной 2·10⁹ — не больше 8·10¹⁸, это меньше предела int64 (около 9,2·10¹⁸). Промежуточные суммы шнурков могут выйти за предел, но знаковые целые в Go при переполнении считаются по модулю 2⁶⁴, и итог, который сам помещается в int64, выходит верным. Пятый тест — квадрат во всё поле: внутри 3 999 999 996 000 000 001 узел.
5+Решение
6Сложность
O(n log C), где C ≤ 2·10⁹ — наибольшая разность координат: на каждую сторону одно произведение и один алгоритм Евклида, которому хватает O(log C) шагов.
7Типичные ошибки
- На заборе только вершины. Самое частое упрощение: B = n. Но длинная сторона проходит через множество узлов: у треугольника из второго теста вершин три, а узлов на границе девять. Это неверное решение задачи, его ловит уже пример.
- Площадь через
float. Числа до 8·10¹⁸ не помещаются в мантиссуdouble(точно до 2⁵³ ≈ 9·10¹⁵), и последние цифры ответа поедут. Считайте удвоенную площадь в целых и делите на два только в самом конце. - Забыли модуль. Обход по часовой стрелке даёт отрицательную сумму шнурков, и без модуля число узлов внутри выйдет отрицательным.
- Своя проверка «точка внутри» для каждого узла. Верно, но узлов бывает 4·10¹⁸. Даже в районе из третьего теста их 23 миллиона, и для каждого — проход по 536 сторонам: больше десяти миллиардов действий.