COI '14 #4 Sir

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

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).

The image corresponds to the first sample test. The dotted line marks Stjepan's cut.

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 N – the number of vertices of the convex polygon representing the cheese.

Each of the following N lines contains two integers X_i and Y_i – coordinates of the i^\text{th} polygon vertex.

The following line contains the integer M – the number of peppers.

Each of the following M lines contains two integers X_i and Y_i – coordinates of the i^\text{th} 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 0.

Constraints

For all subtasks:

The coordinates will be from the interval [-10^9, 10^9].

Subtask Score Constraints
1 12 4 \le N \le 300, 1 \le M \le 300
2 39 4 \le N \le 3\,000, 1 \le M \le 3\,000
3 49 4 \le N \le 300\,000, 1 \le M \le 300\,000

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 2 to vertex 5.

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 1 to vertex 3.


Comments

There are no comments at the moment.