весна 13: Тур 20.03.2013

На плоскости заданы две фигуры, ограниченные выпуклыми многоугольниками. Фигуры расположены таким образом, что их вершины не совпадают, а контуры имеют ровно 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₁ y₁ x₂ y₂. Координаты требуется выводить с точностью 10^-3. Координаты точек должны быть положительны и не превышают 1000.

Пример