#P1474. Video Surveillance
Video Surveillance
题目描述
你的一位朋友在著名的Star-Buy百货公司担任安全主管,他的任务之一是安装视频监控系统,确保商场各楼层顾客(当然还有商品)的安全。由于公司预算有限,每层楼只能安装一个摄像头,但该摄像头可以360度旋转。
第一个问题是确定每层楼的摄像头安装位置,唯一要求是从该位置必须能看到房间的所有区域。如下图所示,左图的楼层可以从圆点位置完全监控,而右图不存在这样的位置——给定位置无法看到楼层的左下角区域。
在安装摄像头之前,你的朋友想先知道是否存在合适的安装位置。因此请你编写程序,根据楼层平面图判断是否存在一个可以监控整个楼层的位置。所有楼层平面图都是矩形多边形(rectangular polygon),其边互不相交,仅在顶点处相连,且边交替为水平和垂直方向。
输入格式
输入包含多个楼层描述:
- 每个描述以顶点数n开头(4 ≤ n ≤ 100)。
- 接下来n行每行包含两个整数,按顺时针顺序给出n个顶点的(x, y)坐标。所有顶点互不相同,且均为多边形的拐角。
- 边交替为水平和垂直方向(即矩形多边形的特性)。
- 输入以n=0结束。
输出格式
对每个测试用例:
- 首先输出楼层编号,如样例所示。
- 若存在可监控整个楼层的位置,输出“Surveillance is possible.”;否则输出“Surveillance is impossible.”。
- 每个测试用例后输出空行。
输入样例1
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
输出样例1
Floor #1
Surveillance is possible.
Floor #2
Surveillance is impossible.
题目来源
1997年西南欧洲区域竞赛(Southwestern European Regional Contest)