408363: GYM103107 C Cookie

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Cookietime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Little G loves cookies.

One day, he bought a bag of cookies and started eating. The shape of each cookie can be approximately regarded as a convex polygon in 2D coordinate system. Unconsciously, a few cookies fell to the ground and each of them broke into two pieces. The broken pieces can be regarded as simple polygons.

Little G didn't want them to go to waste. So, he randomly picked two pieces from the ground and try to restore the original cookie by translating one of the pieces.

Little G is poor at geometry, it takes long time for him to do this or figure out it's just impossible to form a convex polygon using the two simple polygons. Please write a program to help him.

Note that after combining, the overlapping edges of two polygons need to correspond one to one. One edge matching two or more edges of another polygon is illegal.

The graph above shows one illegal situation for matching (a). The situation (b) of the graph is illegal because the right edge of the first square matches two edges of the other polygon. The situation (c) is legal.

Input

The first line contains an integer $$$n ~ (3 \leq n \leq 2000)$$$, indicating the number of the vertexes of the first simple polygon.

Then the following $$$n$$$ lines describes the coordinates of the $$$n$$$ vertexes in counter-clockwise order. Each line contains only two integers $$$x_i, y_i ~ (0 \leq x_i,y_i \leq 10^9)$$$.

The next line contains an integer $$$m ~ (3 \leq m \leq 2000)$$$, indicating the number of the vertexes of the second simple polygon.

Then the following $$$m$$$ lines describes the coordinates of the $$$m$$$ vertexes in counter-clockwise order. Each line contains only two integers $$$x_i, y_i ~ (0 \leq x_i,y_i \leq 10^9)$$$.

Output

One line with a single string yes or no. Print yes if these two polygons can form a convex polygon by translating one of them, otherwise print no.

ExampleInput
8
20 0
18 15
12 17
6 9
10 6
12 8
12 16
17 8
9
11 18
2 15
9 1
19 1
16 9
11 17
11 9
9 7
5 10
Output
yes
Note

The graph below describes the sample where $$$P_1, P_2, \cdots, P_8$$$ is the $$$8$$$ points for the first polygon and $$$Q_1, Q_2, \cdots, Q_9$$$ is the $$$9$$$ points for the second polygon respectively.

加入题单

上一题 下一题 算法标签: