Перетин неопуклих многокутників#4389
Більшість програм для малювання або ілюстрування мають прості інструменти для створення багатокутних об'єктів. Кращі з них можуть знаходити області, які є перетином двох багатокутників. На зображенні нижче показано два багатокутники: один — це п'ятикутник, а інший — трикутник. Їхній перетин складається з двох темних областей.
IBM щойно найняла вас у команду програмістів, яка створюватиме дуже складну програму для малювання/ілюстрування. Ваше завдання — написати частину програми, що працює з перетинами багатокутників. Ваш начальник повідомив, що слід відкласти роботу над інтерфейсом користувача та зосередитись лише на геометричному представленні перетинів.
Багатокутник на декартовій площині можна подати послідовністю точок, які є його вершинами. Вершини у цій послідовності подано в тому порядку, в якому вони проходяться при обході багатокутника за годинниковою стрілкою; тобто будь-які дві сусідні вершини у послідовності є кінцями відрізка, який є однією зі сторін багатокутника. Остання та перша вершини у послідовності також є кінцями сторони. Вершини визначаються своїми координатами та . Вважайте, що для кожного багатокутника справджуються такі умови:
Жодна точка не буде вершиною (в одному багатокутнику) більше одного разу.
Дві сторони можуть перетинатися лише у спільній вершині (кінцевій точці).
Кут між будь-якими двома сторонами зі спільною вершиною більший за та менший за градусів.
Багатокутник має принаймні вершини.
Перетин двох багатокутників складається з або більше зв'язаних областей. Ваше завдання — взяти два багатокутники та визначити області їхнього перетину, що самі є багатокутниками й задовольняють наведені вище критерії.
Вхідні дані містять кілька наборів, кожен з яких складається з двох багатокутників. Кожен багатокутник задається послідовністю чисел:
n,\ x_1,\ y_1,\ x_2,\ y_2,\ \ldots,\ x_n,\ y_n
де ціле число — це кількість вершин багатокутника, а дійсні координати (x_1, y_1) до (x_n, y_n) — вершини на межі. Кінець введення позначається двома нулями для значення . Ці два нулі лише відмічають кінець даних і не слід їх трактувати як окремий набір даних.
Для кожного набору даних ваша програма повинна вивести його номер (Data set 1, Data set 2 тощо) та кількість областей у перетині двох багатокутників. Позначте кожну область у наборі даних (Region 1, Region 2 тощо) і вкажіть її вершини у тому порядку, в якому вони проходяться обхідним шляхом (за або проти годинникової стрілки) по межі області. Першою слід вивести вершину з найменшою -координатою (при рівності — з найменшою -координатою). Жодна область не повинна містити вироджених частин (які складаються із суміжних сторін із кутом перетину ). Якщо три кінці двох суміжних сторін колінеарні, такі сторони слід злити в одну. Виводьте кожну вершину у стандартному вигляді , де та мають дві цифри після десяткової крапки. Наведений нижче вхід містить рівно один набір даних (який відповідає ілюстрації на початку умови задачі).
Приклад 1