cho.sh

Convex Polygon Intersection Area

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

Medium7GeometryDivide and conquerMathNo attempts yetTime limit2sMemory limit128 MB

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.