1361 - Convex

Time Limit : 3 Second

Memory Limit : 256 MB

Submission: 42

Solved: 8

Description
A convex polygon is a simple polygon whose interior is a convex set.[1] The following properties of a simple polygon are all equivalent to convexity:

Every internal angle is less than 180 degrees.
Every line segment between two vertices remains inside or on the boundary of the polygon.
A simple polygon is strictly convex if every internal angle is strictly less than 180 degrees. Equivalently, a polygon is strictly convex if every line segment between two nonadjacent vertices of the polygon is strictly interior to the polygon except at its endpoints.
                                                                    —from Wikipedia

There are two convex polygons, A and B, on the plane. We want to know whether these two polygons intersection or overlap after every time we moving them.
Input
The input contains multiple test cases, for each test case, the first line is two integers, N(N ≦ 50000), M (M ≦ 50000)and K(K ≦ 10000), N is the number of points of convex A, M is the number of points of convex B, K is the number of move operation. N + M + K lines follow, the first N lines describes the coordinates of convex A in anti-clock wise, then the next M lines describes the coordinates of convex B in anti-clock wise, the last K lines is the move operations. “A x y” means move A with (x, y). “B x y” means move B with (x, y).
Output
For each test case, the output should contain K+1 lines, the first line is whether A and B intersect or overlap in the beginning, then K lines follow. Output Yes or No to figure out whether A and B intersect or overlap or not after each operation.
sample input
3  3  3
0.0  0.0
2.0  0.0
1.0  1.0
2.0  0.0
4.0  0.0
3.0  1.0
B  -1.0  0.0
B  0.5  0.5
A  -1.0  0.5
sample output
Yes
Yes
Yes
No
hint
source
中国地质大学(武汉)第七届ACM程序设计大赛暨华中地区部属高校ACM邀请赛
© 2015 HUST ACMICPC TEAM. All Right Reserved.