Division of Polygons#4518
On a plane, there are two shapes, each bounded by a convex polygon. These shapes are positioned such that their vertices do not overlap, and their boundaries intersect at exactly points.
We will divide the plane with an arbitrary line. One half-plane will be associated with the first shape, and the other half-plane with the second shape. The separation defect is defined as the sum of the area of the first shape that lies on the half-plane of the second shape and the area of the second shape that lies on the half-plane of the first shape. Out of the two possible ways to assign half-planes to shapes, we choose the one that results in the smaller defect.
For instance, the illustration shows a line that separates the polygons. The defect for this separation (considering both possible assignments) is calculated as: (D) + (C + E) and (A + D) + (B + C). From the illustration, D + C + E is smaller, so the defect for this line is D + C + E.
Write a program that, given two polygons, determines the line that results in the smallest separation defect.
The first line contains an integer (3 \le N \le 20) - the number of vertices of the first polygon. The next lines provide pairs of integers representing the coordinates of the vertices of the first polygon in order. The (N + 2)-th line contains the integer (3 \le M \le 20) - the number of vertices of the second polygon. The following lines provide the coordinates of its vertices in the same order as the first polygon. The coordinates are positive integers not exceeding .
Output a single line with two pairs of numbers - the coordinates of two points that uniquely define the line with the smallest separation defect. The numbers should be in the order: x_1\ y_1\ x_2\ y_2. The coordinates should be precise to 10^{-3}. The coordinates must be positive and not exceed .
Example 1