eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Разділення многокутників

Разділення многокутників

\includegraphics{https://static.e-olymp.com/content/fe/fe5be9461bffd46eaa7297920cec9296c7e137ae.jpg} На площині задано дві фігури, що обмежені опуклими многокутниками. Фігури розташовані таким чином, що їх вершини не співпадають, а контури мають рівно \textbf{2} точки перетину. Довільним чином розділимо площину прямою. Будемо вважати, що півплощина з одного боку прямої відповідає першій фігурі, а з іншого боку -- другій фігурі. Визначимо поняття дефекту розділення -- сума площі першої фігури, що розташована на півплощині другої фігури, та площі другої фігури, що розташована на півплощині першої фігури. З двох можливих відповідностей півплощин до фігур оберемо таку відповідність, де значення дефекту менше. Наприклад, на рисунку зображена пряма, що задає певне розділення многокутників. Оцінка дефекту цього розділення (два випадки відповідності): \textbf{(D) + (C + E)} та \textbf{(A + D) + (B + C)}. З рисунку, \textbf{D + C + E} менше, отже, загалом, оцінка розбиття дефекту розділення утвореного цією прямою є \textbf{D + C + E}. Напишіть програму, яка за заданими двома многокутниками знаходить пряму, яка утворює розділення з найменшим дефектом. \InputFile Перший рядок містить одне ціле число \textbf{N }(\textbf{3 }≤ \textbf{N }≤ \textbf{20}) - кількість вершин першого многокутника. Наступні \textbf{N} рядків містять пари цілих чисел -- координати вершин першого многокутника у порядку обходу. (\textbf{N + 2})\textbf{ }-ий рядок файлу містить число \textbf{M }(\textbf{3 }≤ \textbf{M }≤ \textbf{20}) - кількість вершин другого многокутника. Наступні \textbf{M} рядків містять його координати задані таким же чином, як і для першого многокутника. Координати точок додатні і не перевищують \textbf{1000}. \OutputFile Вивести в одному рядку дві пари чисел - координати двох точок, які однозначно задають розділення (пряму) з найменшим дефектом. Числа потрібно виводити у порядку: \textbf{x_1 y_1 x_2 y_2}. Координати потрібно виводити з точністю \textbf{10^\{-3\}}. Координати точок повинні бути додатними і не перевищувати \textbf{1000}.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3
2 1
3 3
4 1
3
5 2
3 2
4 3
Вихідні дані #1
2 5 4 1
Автор Богдан Рубльов,Тарас Галковський
Джерело 2007 XX Всеукраїнська олімпіада з інформатики, Кременчук, Квітень 10 - 16, тур 2