Площадь забора
Вокруг точек на плоскости натянули самый короткий выпуклый забор — выпуклую оболочку. Сколько у забора углов и какова площадь внутри? Точки, лежащие ровно на стороне забора, углами не считаются. Чтобы ответ был точным, выведите удвоенную площадь: для целых координат это целое число.
Третий тест — все землетрясения силой от пяти баллов за 2015–2025 годы из каталога USGS, координаты в сотых долях градуса.
Вход
В первой строке n (1 ≤ n ≤ 200 000), дальше n строк с целыми координатами x, y (|x|, |y| ≤ 10⁹). Точки могут совпадать.
Выход
Два числа: количество вершин оболочки и её удвоенную площадь. Если все точки на одной прямой или совпадают, площадь равна 0, а вершин — 1 или 2 (крайние точки).
Примеры
Пример 1
9 0 0 4 0 4 3 0 3 2 1 1 2 2 0 4 3 3 1
4 24
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Оболочка строится монотонной цепочкой из статьи. Подумайте о двух вещах: что делать с тремя точками на одной прямой и не переполнится ли что-нибудь при координатах до 10⁹.
2Идея
Строим оболочку с условием «≤ 0» в цикле: точки на ребре выбрасываются, и в ответе только настоящие углы. Удвоенную площадь считаем векторными произведениями — сумма целых чисел, без деления и без дробей.
3Разбор
Площадь удобно считать «веером» треугольников из первой вершины: 2S = Σ cross(h₀, hi, hi+1). Вершины идут против часовой стрелки, поэтому все слагаемые положительны, и промежуточная сумма никогда не превышает итоговую — не больше 2·(2·10⁹)² = 8·10¹⁸. Это помещается в int64 (до 9,2·10¹⁸). Обычная формула шнурков с произведениями xi·yi+1 складывает слагаемые разных знаков, и её промежуточные суммы в Go могут переполниться.
В векторном произведении каждая разность координат не больше 2·10⁹, произведение — 4·10¹⁸, разность двух произведений — 8·10¹⁸: тоже помещается. Python о переполнении не думает вовсе.
Крайние случаи: одна точка, все точки совпадают, все на одной прямой — оболочка вырождается в точку или отрезок, площадь ноль.
3+Решение
4Сложность
O(n log n) на сортировку и O(n) на проход и площадь.
5Типичные ошибки
- «< 0» вместо «≤ 0». Точки на сторонах остаются в оболочке и считаются углами. Шестой тест — квадрат, на каждой стороне которого тысяча точек.
- Площадь через float. Половинки и деление на два дают дроби; удвоенная площадь — целое число, его и выводим.
- Переполнение в Go. Формула шнурков на координатах ±10⁹ может переполнить промежуточную сумму. Веер из первой вершины — нет.