Максимизируя КПД, продолжаю разбирать популярные задачи с низким процентом решаемости. На очереди задача на геометрию:
Неудивительно, почему эту задачу решают с большим количеством ошибок. Здесь и не очень удобное представление входных данных, и тонкие моменты про границу участка, и координаты до 50000, которые при перемножении как раз приводят к переполнению типа int.
Но количество дачников не очень большое, значит решать можно на Python. Начнём со считывания данных:
Так как результат по каждому дачнику не зависит от остальных, можно обрабатывать их по отдельности, накапливая сумму в result для ответа.
Теперь считаем данные по каждому дачнику и разложим их удобным нам способом:
Сначала всё положим в один список, достанем из него координаты самого дачника, а координаты углов его участка разложим по двух спискам, используя слайсы.
Как же проверить, что точка находится внутри прямоугольника (или многоугольника в общем случае)? Одним из простых способов является вычисление суммы площадей треугольников, на которые разбивается многоугольник, если все его углы соединить с данной точкой.
Наглядно видно, что если точка находится внутри многоугольника, то сумма площадей треугольников будет равна площади этого многоугольника. Если же точка вне, тогда в сумму войдут ещё куски, которые находятся за границей многоугольника.
Со средней школы нам известна формула Герона, которая позволяет найти площадь треугольника по координатам его вершин. Но она довольно сложная, к тому же там используется взятие квадратного корня, что потенциально может приводить к ошибкам округления.
Однако на ряду с операцией скалярного произведения векторов:
есть операция косого произведения векторов (в трёхмерном случае - это векторное произведение):
Если посмотреть на правую часть равенства, то можно увидеть формулу площади параллелограмма, образованного данными векторами. А значит площадь треугольника будет в два раза меньше. Единственным важным моментом, на который стоит обратить внимание, заключается в том, что площадь может получиться отрицательной (а такое в природе запрещено). Дело в том, что эта формула даёт не просто площадь, а ориентированную площадь (знак зависит от направления обхода - по часовой стрелке или против). Значит для обычной жизни надо просто брать абсолютное значение этой величины.
Напишем соответствующие функции (они очень пригодятся в других задачах):
При вычислении площади я не стал делить пополам, потому что тогда получится дробное число, просто буду считать, что функция вычисляет площадь параллелограмма:
Здесь смущает лишь то, что функция принимает координаты трёх точек вместо четырёх, но для вычисления площади её положение не имеет значения (это утверждение верно исключительно для параллелограмма, но не произвольного четырёхугольника).
После такой подготовки можем продолжить решать задачу: пройдёмся по всем вершинам участка и посчитаем площадь треугольника, образованного данной вершиной, предыдущей вершиной и координатой дачника:
Осталось сравнить полученную сумму с площадью прямоугольника (на самом деле с удвоенной, потому что в get_square не делили пополам). А площадь прямоугольника вычислим той же функцией get_square, потому что прямоугольник - это частный случай параллелограмма, для этого передадим ей на вход любые три его вершины:
Осталось вывести ответ:
Сегодня мы узнали ещё одну операцию с векторами и научились просто вычислять площадь треугольника (и параллелограмма) без формулы Герона. И вообще, с помощью косого произведения можно вычислять много разных штук в геометрии. Например, проверять многоугольник на выпуклость.
Предыдущий выпуск: Задача 9. Домашнее задание
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.