Under construction

Still being built. Things may change

Video Surveillance

Time limit1sMemory limit128 MB

Summary
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 nn of vertices that bound the floor (4≤n≤1004 \le n \le 100). Each of the next nn lines contains two integers: the xx and yy 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 00 marks the end of the input.

Output

For each floor, first print a line Floor #k, where kk is the floor number counting from 11. 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.

Examples3

  1. Example 1

    Input
    4
    0 0
    0 1
    1 1
    1 0
    8
    0 0
    0 2
    1 2
    1 1
    2 1
    2 2
    3 2
    3 0
    0
    
    Expected output
    Floor #1
    Surveillance is possible.
    
    Floor #2
    Surveillance is impossible.
    
  2. Example 2

    Input
    4
    0 0
    0 1
    1 1
    1 0
    0
    
    Expected output
    Floor #1
    Surveillance is possible.
    
  3. Example 3

    Input
    6
    0 0
    0 2
    1 2
    1 1
    2 1
    2 0
    0
    
    Expected output
    Floor #1
    Surveillance is possible.