ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102935
Темы:    [ Прямая и отрезок ]
[ Площадь ]
Сложность: 3+
Классы:
Название задачи: Пересечение многоугольников .
В корзину
Прислать комментарий

Условие

Два многоугольника на плоскости заданы координатами своих вершин. Требуется вычислить площадь пересечения этих многоугольников, то есть сумму площадей тех кусков, которые образуются при их пересечении и принадлежат каждому из них. При этом вы можете предполагать, что: 
    А) Многоугольники выпуклые, а координаты их вершин даны в произвольном порядке.
    Б) Хотя бы один из многоугольников невыпуклый, но известно, что у каждого из многоугольников не более одного угла, большего 180 градусов, а координаты вершин даны в порядке обхода по часовой стрелке.
Ваша программа по входным данным должна сама определить, какой из этих двух случаев имеет место.

Входные данные

Первая строка входного файла содержит целое число N – количество вершин в первом многоугольнике (3 ≤ N ≤ 50). Во второй строке записаны координаты этих вершин. Третья и четвертая строки таким же образом задают второй многоугольник. Координаты всех вершин являются целыми числами из диапазона [-32768, 32767].

Выходные данные

Выведите в выходной файл искомую площадь не менее чем с 6 верными значащими цифрами.

Пример входного файла

3
0 3 0 -3 -3 0
5
-1 1 2 1 1 0 2 -1 -1 -1

Пример выходного файла

2.0

Решение

Скачать архив тестов и решений

Отсортируем вершины каждого из многоугольников по полярному углу относительно его центра масс. Если в результате получились два выпуклых многоугольника (для проверки выпуклости используйте критерий из задачи 4.1), значит нам предстоит решать пункт А, иначе – пункт Б. 

Разберем пункт А. Очевидно, что пересечение двух выпуклых многоугольников также является выпуклым многоугольником. Какие точки будут его вершинами? Во-первых, все точки пересечения двух многоугольников. Чтобы их найти, нужно пересечь все стороны одного многоугольника со всеми сторонами другого. Во-вторых, все вершины первого многоугольника, принадлежащие второму, и наоборот, все вершины второго, принадлежащие первому. Определив все вершины пересечения, упорядочим их, отсортировав по полярному углу относительно центра масс. Далее считаем площадь получившегося многоугольника. 

Пункт Б сводится к пункту А следующим образом. Прямая, проведенная через любую из сторон угла, большего 180 градусов, разбивает невыпуклый многоугольник на два выпуклых. Пересекая получившиеся выпуклые многоугольники (как в пункте А) и суммируя площади их пересечений, найдем ответ на пункт Б.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 4
Название Вычислительная геометрия
Задача
Номер 5

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .