Video Surveillance
Time limit1sMemory limit128 MB
Given a rectilinear simple polygon, decide whether one point exists from which the whole interior is visible.
- Level
Hard8 of 10
- Topics
- Geometry, Implementation, Greedy, Array
- Solved
- No attempts yet
Problem
A friend of yours has just been hired as a security officer at a large department store. One of the tasks is to install a video surveillance system that keeps both the customers and the merchandise safe on every one of the store's many floors. Because the budget is limited, each floor gets exactly one camera, but a camera can rotate to look in any direction.
The question is where to place the camera on each floor. The only requirement is that every part of the floor must be visible from that single point. For some floor plans such a point exists; for others it does not — a recessed part of the floor may stay hidden no matter which single point you choose.
Before installing the cameras, your friend wants to know, floor by floor, whether a suitable point exists at all. Write a program that, given a floor plan, decides whether there is a single point from which the entire floor is visible.
Every floor plan is a rectilinear polygon: its edges alternate between horizontal and vertical, no two edges cross, and edges meet only at corners.
Input
The input contains several floor descriptions. Each description begins with the number of vertices that bound the floor (). Each of the next lines contains two integers: the and coordinates of one vertex, listed in clockwise order. All vertices are distinct and are corners of the polygon, so the edges alternate between horizontal and vertical.
A line containing a single marks the end of the input.
Output
For each floor, first print a line Floor #k, where is the floor number counting from . On the next line print Surveillance is possible. if some single point can see the entire floor, or Surveillance is impossible. otherwise. Print a blank line between the results of consecutive floors.