Krešo has bought some delicious cheese with peppers, but Stjepan doesn't really like peppers so he's trying to cut a piece that doesn't contain any peppers.
Krešo's cheese has the shape of a convex polygon, and each pepper is one point on the inside of the polygon. Stjepan cuts the cheese exactly once in such a way that he chooses two vertices of the polygon that are not adjacent and cuts along the line segment connecting them. Stjepan then takes the freshly cut part without any peppers (on the inside nor on the edges).
Write a programme that will determine whether Stjepan can cut a piece of cheese without any peppers. If he can, determine the maximum possible area of the piece of cheese without peppers that Stjepan can cut.
Input Specification
The first line of input contains the integer – the number of vertices of the convex polygon representing the cheese.
Each of the following lines contains two integers and – coordinates of the polygon vertex.
The following line contains the integer – the number of peppers.
Each of the following lines contains two integers and – coordinates of the peppers.
The polygon vertices are given in counter-clockwise order and form a convex polygon. None two adjacent edges are parallel.
All peppers are located in different coordinates in the inside of the polygon (they will not be located on the edge or outside of the polygon).
Output Specification
The first and only line of output must contain an integer – twice the maximum possible area (the double area is always going to be an integer).
If it isn't possible to cut a piece of cheese without peppers in one move, output .
Constraints
For all subtasks:
The coordinates will be from the interval .
Subtask | Score | Constraints |
---|---|---|
, | ||
, | ||
, |
Sample Input 1
5
0 1
3 0
4 2
2 3
0 3
3
2 1
3 1
3 2
Sample Output 1
4
Sample Input 2
6
-3 3
-3 -4
-2 -5
2 -5
3 -4
3 3
7
1 0
0 -1
0 -3
2 0
0 0
0 2
-1 0
Sample Output 2
10
Explanation for Sample Output 2
Stjepan cuts from vertex to vertex .
Sample Input 3
6
0 3
-1 2
-1 -2
0 -3
1 -2
1 2
1
0 0
Sample Output 3
4
Explanation for Sample Output 3
Stjepan cuts from vertex to vertex .
Comments