Under construction

Still being built. Things may change

Convex Polygon Intersection Area

Time limit2sMemory limit128 MB

Summary
Given two convex polygons with vertices in counterclockwise order, compute the exact area of their intersection region within a tight error tolerance.
Level

Medium7 of 10

Topics
Geometry, Divide and conquer, Math
Solved
No attempts yet

Problem

Two convex polygons are given. Both polygons have nonzero area, and no vertex of either polygon lies on an edge of the other polygon.

Write a program that computes the area of the region where the two polygons overlap.

Input

The first line contains N, the number of vertices of the first convex polygon, and M, the number of vertices of the second convex polygon. N and M are positive integers not greater than 100.

The next N lines contain the vertices of the first convex polygon in counterclockwise order. The following M lines contain the vertices of the second convex polygon in counterclockwise order.

Every coordinate is an integer whose absolute value is at most 1,000. Each convex polygon has nonzero area.

Output

Print the area of the region where the two polygons overlap. An absolute or relative error of at most 10^-9 is accepted.

Examples4

  1. Example 1

    Input
    3 4
0 0
2 0
0 3
1 1
3 1
3 3
1 3
    Expected output
    0.08333333333333326

  2. Example 2

    Input
    4 8
-1 -1
1 -1
1 1
-1 1
-2 -2
0 -2
2 -2
2 0
2 2
0 2
-2 2
-2 0
    Expected output
    4.0

  3. Example 3

    Input
    3 3
-1 -1
-2 -1
-1 -2
1 1
2 1
1 2
    Expected output
    0.0

  4. Example 4

    Input
    6 4
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
0 -3
1 -1
2 2
-1 0
    Expected output
    5.233333333333333