A. Area in Convex
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Today, oToToT received two convex polygons, denoted as $$$A$$$ and $$$B$$$, as his toys. After playing with them for a while, oToToT accidentally dropped the convex polygon $$$B$$$ into a puddle of paint! As a result, any area covered by convex polygon $$$B$$$ will be colored.

Being an enthusiastic competitive programmer, oToToT immediately came up with a question: If convex polygon $$$B$$$ is translated (no rotation allowed) inside convex polygon $$$A$$$, what is the area that is possible to be colored by convex polygon $$$B$$$?

However, oToToT recently encountered a dreadful 3D geometry problem, Codeforces 102452F, hence doesn't want to touch any computational geometry problem recently. Therefore, he entrusts you, who is forced to participate in this contest, to help solve the problem.

Note: We say convex polygon $$$B$$$ is inside convex polygon $$$A$$$ when all points of convex polygon $$$B$$$ lie within convex polygon $$$A$$$.

Input

The input begins with two integers $$$N$$$ and $$$M$$$, denoting number of points of convex polygon $$$A$$$ and convex polygon $$$B$$$, respectively.

Then, $$$N$$$ lines are provided, each containing two integers $$$x_i$$$ and $$$y_i$$$, representing the $$$i$$$-th point of convex polygon $$$A$$$.

Following that, $$$M$$$ lines are provided, each containing two integers $$$p_i$$$ and $$$q_i$$$, representing the $$$i$$$-th points of convex polygon $$$B$$$.

  • $$$3 \leq N, M \leq 10^4$$$
  • $$$0 \leq |x_i|, |y_i|, |p_i|, |q_i| \leq 10^6$$$
  • The points of the two convex polygons are given in counterclockwise order.
  • It is guaranteed that $$$B$$$ can be placed inside $$$A$$$.
  • Under the condition that $$$B$$$ remains inside $$$A$$$, there exist two non-parallel directions in which $$$B$$$ can be moved a positive distance.
  • Let $$$C$$$ be the maximum absolute value among all coordinates. It is guaranteed that $$$C^2$$$ is no more than $$$10^5$$$ times the area of $$$B$$$.
Output

Output a real number in a single line, representing the area that can be colored within convex polygon $$$A$$$ by convex polygon $$$B$$$. Your answer will be considered correct if the relative or absolute error compared to the correct answer is within $$$10^{-6}$$$.

Examples
Input
4 3
0 0
10 0
10 5
0 5
4 0
6 0
5 4
Output
46.000000000000000
Input
6 4
-2 2
5 0
10 4
5 12
0 10
-3 5
1 7
3 7
3 9
1 9
Output
94.677042606516291