시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 46 | 18 | 10 | 27.778% |
Yesterday Little John had a test on geometry. The description of the most difficult problem follows. Given two triangles A and B, calculate the area of region A + B, which is defined as follows: A + B = {p1 + p2 : p1 ∈ A, p2 ∈ B}. For example, if A has the vertices (0, 0), (0, 2), (2, 0) and B has the vertices (0, 0), (0, 1), (3, 0), then A + B is a polygon with the vertices (0, 0), (0, 3), (3, 2) and (5, 0), so its area is 9.5.
Afterwards, John started to wonder how to solve a modified problem - "How to calculate area of A + B, if A and B are arbitrary convex polygons". Little John has a test on biology tomorrow and has no time to solve this problem himself. He asked you for help in solving this task.
Write a program, which:
The first line of the standard input contains two integers n and m (3 ≤ n, m ≤ 100 000) separated with a single space and denoting the numbers of vertices of polygons A and B. In the second line there are n pairs of integers (xi, yi) (-100 000 000 ≤ xi, yi ≤ 100 000 000), denoting the coordinates of consecutive vertices of the polygon A (in the clockwise order). In the third line there are m pairs of integers (xi, yi) (-100 000 000 ≤ xi, yi ≤ 100 000 000) denoting the coordinates of consecutive vertices of the polygon B (in the clockwise order).
The first and only line should contain one integer - doubled area of A + B.
4 4 0 0 0 1 2 1 2 0 0 0 0 2 1 2 1 0
18
Contest > Algorithmic Engagements > PA 2006 6-3번