2571: Gears
Time Limit: 2 Sec Memory Limit: 256 MBSubmit: 0 Solved: 0
[Submit] [Status] [Web Board] [Creator:]
Description
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:
- the polygons are not necessarily convex;
- points P and Q can be located on the border of or outside their polygons.
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.
Print "YES", if the collision takes place and "NO" otherwise (don't print the quotes).
1 0
4
0 0
1 0
1 5
0 5
9 0
4
9 0
9 -5
10 -5
10 0
YES
0 0
3
1 0
2 -1
2 1
0 0
3
-1 0
-2 1
-2 -1
NO
A polygon is a closed polyline that doesn't intersect itself and doesn't touch itself.
Picture to the first sample:
