Площадь района из нескольких кусков
Земельная служба хранит границу участка как список точек — целые координаты в метрах в своей системе отсчёта. Участок может состоять из нескольких отдельных кусков: так у Медеуского района Алматы кроме основной территории есть микрорайон Алатау, в восьми километрах от остального района. Граница каждого куска — замкнутое кольцо точек. Кольца не пересекаются и не касаются ни себя, ни друг друга, и ни одно не лежит внутри другого — дыр в участках нет. А вот направление обхода у колец любое: как нарисовали, так и хранится.
Найдите площадь каждого участка — точно, без округления. Второй тест — восемь районов Алматы из OpenStreetMap в метрах на сетке карты дорог этого каталога.
Вход
В первой строке число участков q (1 ≤ q ≤ 10 000). Описание участка начинается с числа колец k (k ≥ 1). Каждое кольцо — число точек m (m ≥ 3) и m строк с координатами x y в порядке обхода. Все координаты целые, |x|, |y| ≤ 10⁹. Всего точек во входе не больше 200 000.
Выход
Для каждого участка — его площадь в квадратных метрах. Она всегда целая или полуцелая: выведите целое число или целое число с .5, без лишних нулей.
Примеры
Пример 1
3 1 4 0 0 4 0 4 4 0 4 1 3 0 0 0 3 1 0 2 4 0 0 4 0 4 4 0 4 3 10 0 10 2 12 0
16 1.5 18
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сначала одно кольцо: формула шнурков с целыми числами даёт удвоенную площадь точно. Что она вернёт для кольца, обойдённого по часовой стрелке?
2Подсказка 2
Возьмите участок из двух квадратов, один обойдён против часовой стрелки, другой — по часовой. Что даст сумма шнурков по обоим кольцам сразу?
3Идея
Формула шнурков даёт площадь со знаком: плюс для обхода против часовой стрелки, минус — по часовой. Для одного кольца знак убирает модуль. Но если сложить кольца со знаком и взять модуль в конце, кольца с разным обходом вычтутся друг из друга. Модуль берут у каждого кольца отдельно, и только потом складывают. Удвоенная площадь — целое число, поэтому ответ — либо целое, либо с половинкой.
4Разбор
Для кольца P₀, …, Pm−1 считаем 2S = Σ (xi−1yi − xiyi−1), индексы по кругу. Складываем |2S| по всем кольцам участка в целом числе T. Ответ: T div 2, и если T нечётно, приписываем «.5».
Ровно эта ошибка видна в статье на Медеуском районе: основная часть района обойдена по часовой стрелке и даёт −267,38 км², микрорайон Алатау — против часовой и даёт +5,85 км². Модуль суммы со знаком — 261,53 км², а настоящая площадь — 273,22 км².
Про переполнение в Go. Каждое произведение не больше 10¹⁸ по модулю, а удвоенная площадь участка в квадрате со стороной 2·10⁹ — не больше 8·10¹⁸: это помещается в int64. Промежуточные суммы при этом могут выйти за предел — частичная сумма шнурков равна удвоенной площади веера, который способен намотаться вокруг начала координат несколько раз. Но целые числа со знаком в Go при переполнении не падают, а считаются по модулю 2⁶⁴ (это закреплено в спецификации языка). Сложение и умножение по модулю 2⁶⁴ согласованы с обычными, поэтому итог, который сам помещается в int64, получается верным, как бы ни гуляли промежуточные суммы. Пятый тест — квадрат во всё поле: 4·10¹⁸ м².
4+Решение
5Сложность
O(N), где N — число точек во входе: по одному умножению-вычитанию на сторону.
6Типичные ошибки
- Модуль в конце, а не у каждого кольца. Кольца с разным обходом вычитаются — это неверное решение задачи. Его ловят пример и второй тест.
- Числа с плавающей точкой. При координатах около 10⁹ произведение — около 10¹⁸, а
doubleхранит целые точно только до 2⁵³ ≈ 9·10¹⁵. Последние цифры ответа поедут, и половинку не отличить от целого. Шестой тест — маленькие участки у самого края поля, где это видно сразу. - Вывод «12.0» или «12.50». Нужно ровно «12» или «12.5»: проверка сравнивает строки.