Задача Fence
Два сусіди-фермери отримали сертифікати на право володіння землею.
Кожен з них отримав площу, що має вигляд багатокутника без
самоперетинів, всі кути якого не дорівнюють
180. Межі цих площ задані координатами вершин багатокутника в
прямокутній Декартовій системі координат, що подаються в порядку обходу
багатокутника в деякому напрямку за годинниковою
стрілкою, або проти.
В подальшому виявилось, що ці землі мають спільну частину.
Цікаво, що жодна з вершин багатокутника, що обмежує землі одного з фермерів, не потрапляє на межу
землі іншого.
Фермери вирішили побудувати огорожу навколо
спільної землі, що являє собою деяку множину
многокутників. Для цього треба поставити по одному кілку в кожну вершину
багатокутників, що утворюються при перетині земель. Причому ці багатокутники також без
самоперетинів, та всі його кути не дорівнюють
180.
Технічні умови.
Ви послідовно вводите з клавіатури 2 числа n1 і
n2. (3<=n1, n2<=100) - кількість вершин
багатокутників, що обмежують землі першого та другого фермерів
відповідно. Далі через пропуск вводите координати
(x, y) n1 вершин земель першого фермера. Далі через пропуск вводите координати
(x, y) n2 вершин земель другого фермера.
Всі координати не перевищують 1000 за абсолютною величиною.
Ви виводите на екран шукану кількість кілків.
Приклад 1.
Введення:
5 6 2 2 5 3 6 1 8 4 4 7 2 7 5 10 7 8 8 5 6 4 5 5
Виведення: 5
Приклад 2.
Введення: 6 6 1 4 4 7 6 4 4 2 6 0 4 -2 4 1 6 -3 12 4 7 7 4 4 8 2
Виведення: 8
© LIKT 1998-2018