Пересечение невыпуклых многоугольников
Большинство программ для рисования или иллюстраций имеют простые средства для создания многоугольников. Лучшие из них способны находить область пересечения двух многоугольников. На рисунке ниже изображены два многоугольника, один из которых является пятиугольником, а второй треугольником. Их область пересечения состоит из двух темных областей.
IBM только что нанял Вас как члена группы программистов, которым следует создать очень сложную программу для рисования/иллюстраций. Ваша задача состоит в разработке программы, работающей с пересечениями многоугольников. Ваш босс попросил Вас отвлечься от пользовательского интерфейса и сосредоточиться на геометрическом представлении пересечений.
Многоугольник в декартовой системе координат представляется последовательностью его вершин. Вершины в последовательности задаются в порядке их обхода границы многоугольника по часовой стрелке; таким образом любые две соседние вершины являются концами отрезка - стороны многоугольника. Последняя и первая точки последовательности также являются концами стороны многоугольника. Вершины задаются своими x и y координатами. Следующие утверждения справедливы для каждого многоугольника:
Никакая точка не является вершиной (на одном многоугольнике) более одного раза.
Две стороны могут пересекаться только в общей точке (вершине).
Угол между любыми двумя сторонами с общей вершиной всегда больше 0 и меньше 360 градусов.
Многоугольник содержит как минимум 3 вершины.
Пересечение двух многоугольников состоит из 0 или более связных областей. По заданным двум многоугольникам следует определить области их пересечения.
Входные данные
Входные данны состоят из нескольких тестов, каждый из которых содержит два многоугольника. Каждый многоугольник задается последовательностью чисел:
n, x_1, y_1, x_2, y_2, ..., x_n, y_n
где n - число вершин, а действительные числа с (x_1, y_1) до (x_n, y_n) представляют собой координаты граничных вершин. В конце входных данных задаются два нуля как значения n. Они являются меткой конца данных, и не должны трактоваться как отдельный тест.
Выходные данные
Для каждого теста вывести его номер (Data set 1, Data set 2, и так далее) и число областей в пересечении двух многоугольников. Пронумеруйте каждую область в тесте (Region 1, Region 2, и так далее) и выведите ее вершины в порядке обхода границы области по или против часовой стрелки. Первой следует вывести вершину с наименьшей x координатой (если таковых несколько, то с наименьшей y координатой). Ни одна из областей не должна включать в себя вырожденные участки (содержать соседние стороны угол между которыми равен 0). Если три точки двух соседних сторон коллинеарны, то эти стороны следует объединить в одну. Каждую вершину следует выводить в формате (x, y), где x и y содержат по две десятичные цифры. Приведенный ниже пример содержит один тест (он соответствует картинке в условии задачи).