Picky Eater

Time limit1sMemory limit512 MB

Summary

Cut the convex polygon along one diagonal between nonadjacent vertices and eat the largest piece that contains no olive.

Level: Medium6 of 10
Topics: Geometry, Brute force, Prefix sum
Solved: No attempts yet

Problem

Byeongchan ordered a pizza for his friend Gongchan. Gongchan dislikes olives, so he wants to cut the pizza before eating it.

The pizza is a convex polygon and the olives are stuck inside it. Gongchan picks two vertices that are not adjacent and cuts the pizza once along the straight line through those two vertices. The cut leaves two pieces, and Gongchan eats the piece that holds no olive. If an olive sits on the cutting line, that olive is split in two, so he can eat neither piece.

Byeongchan does not eat much pizza, so Gongchan wants the piece he eats to be as large as possible. Write a program that finds how large a piece Gongchan can cut for himself.

Input

The first line contains the number of pizza vertices $N$ .

Each of the next $N$ lines contains the coordinates $X_i$ , $Y_i$ of one vertex. The vertices are given counterclockwise, and all $N$ interior angles of the pizza are smaller than 180 degrees.

Line $N+2$ contains the number of olives $M$ .

Each of the next $M$ lines contains the coordinates $X_i$ , $Y_i$ of one olive. No olive lies on an edge of the pizza or outside the pizza. An olive is tiny, so treat it as a point.

Output

If Gongchan gets no edible piece no matter how he cuts, print 0.

Otherwise print twice the largest area Gongchan can eat. Think it through and you will see that this value is always an integer.

Constraints

All coordinates are integers between $-10^9$ and $10^9$ . The pizza is a convex polygon, so $N \ge 3$ .

Examples3

Example 1
Input
```
5
0 1
3 0
4 2
2 3
0 3
3
2 1
3 1
3 2
```
Expected output
```
4
```

Example 2

Input

Expected output

Example 3
Input
```
6
0 3
-1 2
-1 -2
0 -3
1 -2
1 2
1
0 0
```
Expected output
```
4
```