Problem G
Forest Evolution

Photo by Patrick Hendry

Ewan is a park ranger, and part of his duty is to observe how the ecosystem changes over time. He has just detected that a group of pine trees and aspens have started to share the same space. Before, there was a clear line between the species.

This isn’t unusual, but Ewan is a bit curious about how this will evolve in the future. To track it, he wants to know how much of the area is covered by both species right now.

Input

The input begins with a single line with two integers $P$ and $A$: the number of pine trees and aspens, respectively. Then follow $P + A$ lines, one line for each tree. The first $P$ of these lines contain locations for the pine trees, and the remaining $A$ lines contain locations for the aspens.

Each tree is represented by two real numbers $x_ i$ and $y_ i$, representing the location of the tree on a 2D map in metres.

Output

Output the area covered by both species in square metres. Your answer must have an absolute or relative error of at most $10^{-3}$.

A point is covered by a species if it is at the edge of or inside a triangle made by three distinct trees of that species.

Limits

• $0 \leq P, A \leq 1\, 000$

• $0.0 \leq x_ i, y_ i \leq 1\, 000.0$

• $0.2 < |x_ i-x_ j|+|y_ i-y_ j|$ for all $0 \leq i < j < P + A$

• Real numbers in the input will have at most $8$ digits after the decimal point

3 3
0.0 6.0
6.0 0.0
6.0 6.0
4.0 4.0
10.0 4.0
4.0 10.0

4.0

6 4
0.67 10.82
5.58 5.43
5.83 10.79
5.70 15.06
10.53 10.05
10.45 5.22
6.76 8.64
8.93 8.45
6.43 5.34
12.34 2.87

10.47478482125473