5392: Gears
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
D. Gears
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
There are two polygons on the plane, A and B. Polygon A rotates around point P, and polygon B rotates around point Q. Each polygon rotates with the constant rotational speed in the clockwise direction around its point, the rotational speed values of the polygons' rotation are equal.
Your task is to determine if there will be a collision between polygons. A collision is a situation when the polygons have at least one common point.
It is guaranteed that at the moment 0 the polygons A and B do not intersect and no polygon is fully contained inside another one.
Note that:
Your task is to determine if there will be a collision between polygons. A collision is a situation when the polygons have at least one common point.
It is guaranteed that at the moment 0 the polygons A and B do not intersect and no polygon is fully contained inside another one.
Note that:
- the polygons are not necessarily convex;
- points P and Q can be located on the border of or outside their polygons.
Input
The first line contains space-separated coordinates of point P.
The second line contains a single integer n (3≤n≤1000)− the number of vertices of polygon A.
Each of the next n lines contains two space-separated integers − the coordinates of the corresponding vertex of polygon A.
The next line is empty.
Then follow space-separated coordinates of point Q.
The next line contains a single integer m (3≤m≤1000)− the number of vertices of polygon B. Next m lines contain the coordinates of the vertices of the polygon B.
The vertices of both polygons are listed in the counterclockwise order. Coordinates of all points are integers, their absolute values don't exceed 104.
Output
Print "YES", if the collision takes place and "NO" otherwise (don't print the quotes).
Examples
Input
1 0 4 0 0 1 0 1 5 0 5 9 0 4 9 0 9 -5 10 -5 10 0
Output
YES
Input
0 0 3 1 0 2 -1 2 1 0 0 3 -1 0 -2 1 -2 -1
Output
NO
Note
A polygon is a closed polyline that doesn't intersect itself and doesn't touch itself.
Picture to the first sample:
输入样例 复制
输出样例 复制