Kattis

# 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

Sample Input 1 Sample Output 1
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

Sample Input 2 Sample Output 2
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