题目名称	877. 闭合的栅栏
输入输出	`fence4.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	11
题目来源	sywgz 于2012-07-11加入
开放分组	全部用户
提交状态
分类标签	USACO 计算几何
	分享题解

通过：4，提交：20，通过率：20%
策	100	0.000 s	0.00 MiB	C++
2279544550	100	0.017 s	0.32 MiB	C++
cstdio	100	0.018 s	0.32 MiB	C++
zhengtn03	100	0.039 s	0.31 MiB	C++
QhelDIV	90	0.008 s	0.33 MiB	C++
mildark	90	0.018 s	0.29 MiB	C++
zhengtn03	90	0.034 s	0.35 MiB	C++
zhengtn03	90	0.042 s	0.35 MiB	C++
sillyrobot	90	0.048 s	0.31 MiB	C
任杰	90	0.133 s	0.33 MiB	C++

关于闭合的栅栏的近10条评论(全部评论)
第九组数据有误。可以在数据中找到这样的两条边：(26,1)->(72,159)和(24,2)->(157,13)，显然它们相交，因此答案应为"NOFENCE"。事实上，这组数据的格式也有问题，看上去似乎是一个n=100的数据的一部分和一个n=199的数据拼接而成。各位自行cheat。 if(n==100){cout<<"4\n45 81 43 188\n43 188 196 112\n196 112 199 -1\n199 -1 0 0\n";return 0;} cstdio 2013-10-27 20:33 1楼

877. 闭合的栅栏

★ 输入文件：fence4.in 输出文件：fence4.out 简单对比
时间限制：1 s 内存限制：128 MiB

USACO/fence4(译 by Jeru)

Closed Fences闭合的栅栏

描述

一个闭合的栅栏是平面上的一些不相交的首尾相连的线段形成的多边形，有N个角(顶点) (3 < N < 200)。顶点不重合，它以逆时针方式以数组{x_i, y_i}给出(i=1,2,...,N)。

每一对相邻的顶点都是一条栅栏。因此共有N条栅栏 (定义x_N+1=x₁, y_N+1=y₁)。

这里有一个栅栏的例子和一个点x,y:

                        * x3,y3
                x5,y5  / 
   x,y *          *   /   
                 /  /     
                /   *       
          x6,y6*   x4,y4     
               |              
               |               
          x1,y1*----------------* x2,y2

请编写一个程序实现下面的任务:

检查输入的顶点列表{xi,yi}, i=1,2,...,N, 判断它是否为一个合法的闭合栅栏。
找出所有可以被站在点(x,y)处的人所能看到的栅栏(忽略人的高度)，因为有的栅栏会被另外的栅栏所挡住。

只有当存在从(x,y)发射的一条射线第一个穿过栅栏i时，栅栏i是可以被看见的。如果栅栏是平行于目光的，它并不认为是可以看见的。在上面的例子里，线段[x3,y3]-[x4,y4], [x5,y5]-[x6,y6], [x6-y6]-[x1,y1]是可以被(x,y)看见的。

格式

PROGRAM NAME: fence4

INPUT FORMAT:

(file fence4.in)

第一行: N, 表示闭合栅栏的顶点数。

第二行: 两个整数x和y，表示观测者的位置。两个整数都是16位的。即2^16，在longlong或longint范围内。

第3到N+2行: 每行一对整数(x,y)表示对应闭合栅栏的第k个顶点的坐标。坐标以逆时针顺序给出。整数绝对值不超过1000。

注意：我添加了该题的新的第12个测试点。如果你认为这个点的数据是错误的，发送邮件到Rob（kolstad@ace.delos.com）在您的邮件主题中一定要包括USACO！

OUTPUT FORMAT:

(file fence4.out)

如果给出的序列不是一个合法的闭合栅栏，那么输出文件只需要输出“NOFENCE”。

栅栏用两端的顶点表示，顶点的输出顺序以输入文件中的顺序为准。把栅栏按照最后一个点在输入文件中的顺序排序。如果两条栅栏的最后一个点是一样的，就以它们第一个点的顺序排序。

SAMPLE INPUT

13
5 5
0 0
7 0
5 2
7 5
5 7
3 5
4 9
1 8
2 5
0 9
-2 7
0 3
-3 1 SAMPLE OUTPUT  
7
0 0 7 0
5 2 7 5
7 5 5 7
5 7 3 5
-2 7 0 3
0 0 -3 1
0 3 -3 1