Перетин неопуклих многокутників
Більшість програм для малювання або іллюстрацій мають прості засоби для створення многокутників. Кращі з них здатні знаходити область перестину двох многокутників. На рисунку нижче зображено два многокутника, один з яких є п'ятикутником, а другий трикутником. Їх область перетину складається з двох темних областей.
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 містять по дві десяткові цифри. Наведений нижче приклад містить один тест (він відповідає картинці з умови задачі).