1302
правки
Изменения
м
Дан[o] Данo 2[<tex>k</tex>] многоугольников. Нужно найти множество многоугольников, являющееся их пересечением.
→Два выпуклых многоугольника
===Постановка задачи===
Многоугольники могут быть невыпуклые и дырявые.
В итоге мы получили набор отрезков {{---}} границу пересечения многоугольников. Из них составим многоугольник, который и будет ответом.
Заметим, что алгоритм работает за линейное (офигеть, да?) время. '''Основная идея {{---}} в том, чтобы следить за областью и понимать, является ли она пересечением или нет.'''
====Два многоугольника====
