Almost Clear
Time limit1sMemory limit128 MB
Given two disjoint convex polygons A and B and a point C outside both, decide whether B hides none, part, or all of A as seen from C.
- Level
Hard8 of 10
- Topics
- Geometry, Binary search, Two pointers, Implementation
- Solved
- No attempts yet
Problem
A museum displays many valuable objects and installs surveillance cameras so that every object can be watched. Your task is to check a single camera against a single obstacle.
In the 2-D plane you are given a convex polygon (the valuable object), a convex polygon (another object), and a point (the camera). Determine how much of polygon is hidden by polygon when the camera is placed at .
Assumptions:
- All coordinates lie in the 2-D plane.
- Polygons and are both convex.
- The camera has infinite range (it can see arbitrarily far).
- The camera can rotate freely through a full 360°.
- The camera cannot move away from point .
- Every position is valid: the two polygons do not intersect, and the camera is never inside either polygon.
A point of polygon is hidden when the straight segment from to passes through polygon . Depending on how much of is hidden, decide whether is fully visible, partially hidden, or completely hidden.
Input
The first line contains an integer (), the number of test cases.
Each test case consists of three lines:
- The first line describes polygon : an integer (), the number of vertices, followed by coordinate pairs listing the vertices in counter-clockwise order.
- The second line describes polygon in exactly the same format.
- The third line contains two integers: the - and -coordinates of the camera .
All coordinates are non-negative and smaller than .
Output
For each test case, print exactly one line:
CLEARif polygon is not obstructed by polygon at all;ALMOST CLEARif polygon is only partially obstructed by polygon ;NO VISIONif polygon is completely hidden by polygon .