A friend of yours has taken the job of security officer at the Star-Buy Company, a famous depart- ment store. One of his tasks is to install a video surveillance system to guarantee the security of the customers (and the security of the merchandise of course) on all of the store's countless floors. As the company has only a limited budget, there will be only one camera on every floor. But these cameras may turn around to look in every direction.

The first problem is to choose where to install the camera for every floor. The only requirement is that every part of the room must be visible from there. In the following figure the left floor can be completely surveyed from the position indicated by a dot, while for the right floor, there is no such position, the given position failing to see the lower left part of the floor. 

Before trying to install the cameras, your friend first wants to know whether there is indeed a suitable position for them. He therefore asks you to write a program that, given a ground plan, de- termines whether there is a position from which the whole floor is visible. All floor ground plans form rectangular polygons, whose edges do not intersect each other and touch each other only at the corners. 

Input

The input contains several floor descriptions. Every description starts with the number n of vertices that bound the floor (4 <= n <= 100). The next n lines contain two integers each, the x and y coordinates for the n vertices, given in clockwise order. All vertices will be distinct and at corners of the polygon. Thus the edges alternate between horizontal and vertical.

A zero value for n indicates the end of the input.

Output

For every test case first output a line with the number of the floor, as shown in the sample output. Then print a line stating "Surveillance is possible." if there exists a position from which the entire floor can be observed, or print "Surveillance is impossible." if there is no such position.

Print a blank line after each test case.

Sample 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

Sample Output

Floor #1
Surveillance is possible. Floor #2
Surveillance is impossible.

题意:给定比较规则的多边形,问是否存在一点P,使得P到所有多边形上的点的路径都是在多边形内部,即是否存在核。

思路:反正是模板题,思路自己百度吧。

update:https://www.cnblogs.com/hua-dong/p/10670137.html

最新文章

  1. 【Django】--ModelForm组件
  2. 2.Java异常学习
  3. hive修改 表/分区语句
  4. tiny_cnn 阅读(1)
  5. 转:RTC搭建android下三层应用程序访问服务器MsSql-客户端
  6. 【转】【公司调查】车来了APP
  7. C语言头文件的作用
  8. 实现textarea限制输入字数
  9. hdu 1284 关于钱币兑换的一系列问题 九度oj 题目1408:吃豆机器人
  10. Linux下搭建Nginx+MySQL+PHP
  11. BZOJ 3653: 谈笑风生(DFS序+可持久化线段树)
  12. 【★】RSA-什么是不对称加密算法?
  13. CSS3中first-child、last-child、nth-child、nth-last-child
  14. [译]Walkthrough: Using MSBuild
  15. Jedis入门
  16. python接口自动化-参数化
  17. Nginx HTTP负载均衡/反向代理的相关参数测试
  18. 平衡二叉树,AVL树之代码篇
  19. SaltStack Pillar 详解
  20. Ubuntu16.04下安装MATLAB 2016b!完美运行

热门文章

  1. 洛谷——P2298 Mzc和男家丁的游戏
  2. luogu P2296 寻找道路
  3. 51 NOD 1383 整数分解为2的幂
  4. java设计模式图
  5. Maven配置将war包部署到Tomcat(tomcat7-maven-plugin)
  6. go语言学习之路三:切片
  7. iinflux数据库使用
  8. spring-quartz定时任务使用小结
  9. 如何正确地在React中处理事件
  10. 疯狂Java学习笔记(77)-----------凝视注意事项