Линия для добавления плоскостей, а для добавления полуплоскости — еще линия от количества вершин в "общем" множестве. Или я неправильно понял?

Есть такой человек, зовут его Per Austrin, он публикует разборы финалов ACM ICPC. В начале каждого разбора он приводит дисклеймер, вот его важная часть:

Also, note that these sketches are just that—sketches. They are not intended to give a complete solution, but rather to outline some approach that can be used to solve the problem. If some of the terminology or algorithms mentioned below are not familiar to you, your favorite search engine should be able to help.

Вам чтение разборов такого формата явно не дается, судя по всему, из-за проблем с последней частью и с самостоятельным мышлением :).

NuM уже объяснил Вам, что многоугольник можно задать множеством полуплоскостей, пересечением которых он является. Т.о. для нахождения пересечения нескольких многоугольников нам нужно объединить множества плоскостей, задающих многоугольники, и выкинуть оттуда лишние полуплоскости. Выкидывание лишних полуплоскостей — это и есть алгоритм пересечения полуплоскостей, который можно реализовать за линию с помощью дека, при условии, что наши полуплоскости отсортированы по углу поворота их нормали. Очевидно, что многоугольник, заданный в фиксированном порядке обхода, можно считать отсортированным множеством полуплоскостей.

Как объединить k отсортированных множеств? Тупой вариант — завести приоритетную очередь, которая будет содержать наименьшие не добавленные в ответ элементы из каждого множества. Более умный вариант (будет работать явно быстрее в случае небольшого k) — на каждом шаге объединять два наименьших множества за линию, пока у нас не останется одно множество (если нужно доказательство — смотрите доказательство алгоритма Хаффмана).