eolymp
bolt
Try our new interface for solving problems
Məsələlər

Разделение многоугольников

Разделение многоугольников

\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{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}.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
3
2 1
3 3
4 1
3
5 2
3 2
4 3
Çıxış verilənləri #1
2 5 4 1
Müəllif Bogdan Rublev, Taras Galkovskiy
Mənbə 2007 XX All-Ukrainian Informatics Olympiad, Kremenchuk, April 10 - 16, Round 2