Задачи
Разделение многоугольников
Разделение многоугольников
\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}.
Входные данные #1
3 2 1 3 3 4 1 3 5 2 3 2 4 3
Выходные данные #1
2 5 4 1