提示: 欢迎访问OurACM平台。
Problem 1379 Minkowski Sum

Accept: 17    Submit: 67
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A polygon consists of all points on or enclosed by its border. A convex polygon has the property that for any two points X and Y of the polygon, the line segment connecting X and Y is inside the polygon. All polygons in this task are convex polygons with at least three vertices, and all vertices in a polygon are different and have integer coordinates. No three vertices of the polygon are collinear. The word "polygon" below always refers to such polygons.

Given two polygons A and B, the Minkowski sum of A and B consists of all the points of the form (x1+x2, y1+y2) where (x1, y1) is a point in A and (x2, y2) is a point in B. It turns out that the Minkowski sum of polygons is also a polygon. The figure below shows an example: two triangles and their Minkowski sum.

Input

There are several test cases in the input. The first line of each test case contains one integer m (3<=m<=3000), representing the number of vertices of polygon A. The following m lines contains two integers each, which describes the coordinates of the vertices, (xi,yi) of polygon A. The (m+2)th line contains one integer n (3<=n<=3000), describes the number of vertices of polygon B. The following n lines contains coordinates of the vertices.

The polygon starts from the first vertex to the second one, then from the second to the third, ..., and so on. At last, it closes from the nth vertex to the first one.

Process to the end of file.

Output

For each case, output only one line containing the number of vertices and area (accurate to three fractional digits) in the Minkowski sum.

Sample Input

3 0 0 1 1 2 3 3 4 5 5 6 6 7

Sample Output

4 2.500

Source

FZU 2005

Submit  Back  Status  Discuss