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邀请赛