Разделение многоугольников
На плоскости заданы две фигуры, ограниченные выпуклыми многоугольниками. Фигуры расположены таким образом, что их вершины не совпадают, а контуры имеют ровно 2 точки пересечения.
Произвольным образом разделим плоскость прямой. Будем считать, что полуплоскость с одной стороны прямой соответствует первой фигуре, а с другой стороны – второй фигуре. Определим понятие дефекта разбиения – сумма площади первой фигуры, которая расположена в полуплоскости второй фигуры, и площади второй фигуры, которая расположена в полуплоскости первой фигуры. Из двух возможных соответствий полуплоскостей к фигурам выберем такое соответствие, где значение дефекта меньше.
Например, на рисунке изображена прямая, которая задает некоторое разделение многоугольников. Оценка дефекта этого разделения (два случая соответствия): (D) + (C + E) и (A + D) + (B + C). Из рисунка, D + C + E меньше, соответственно, в целом, оценка дефекта разделения порожденного этой прямой есть D + C + E.
Напишите программу, которая по заданным двум многоугольником находит прямую, которая образует разделение наименьшего дефекта.
Входные данные
Первая строка содержит одно целое число N (3 ≤ N ≤ 20) - количество вершин первого многоугольника. Последующие N строк содержат пары целых чисел – координаты вершин первого многоугольника в порядке обхода. (N + 2) - ая строка содержит число M (3 ≤ M ≤ 20) - количество вершин второго многоугольника. Последующие M строк содержат его координаты заданные таким же образом, как и для первого многоугольника. Координаты точек положительны и не превышают 1000.
Выходные данные
Вывести в одной строке две пары чисел - координаты двух точек, которые однозначно задают разделение (прямую) с наименьшим дефектом. Числа требуется выводить в порядке: x_1 y_1 x_2 y_2. Координаты требуется выводить с точностью 10^{-3}. Координаты точек должны быть положительны и не превышают 1000.