题目详情
返回题库题目描述
一个闭合的栅栏是平面上的一些不相交的首尾相连的线段形成的多边形，有NN个角(顶点) (3<N<2003<N<200)。 顶点不重合，它以逆时针方式以数组{xixi,yiyi}给出(i=1,2,...,Ni=1,2,...,N)。
每对相邻的顶点定义了围栏的一侧。因此 {xixiyiyixi+1xi+1yi+1yi+1} 是 (1..N1..N) 中所有ii的围栏的一侧。就我们的目的而言，N+1=1N+1=1，因此使围栏关闭的第一个和最后一个顶点。
* 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)看见的。
输入描述
第一行:N, 表示闭合栅栏的顶点数。
第二行:两个整数x和y，表示观测者的位置。两个整数都是16位的。
第3到N+2行:每行一对整数(x,y)表示对应闭合栅栏的第k个顶点的坐标。坐标以逆时针顺序给出。整数绝对值不超过1000。
输出描述
如果给出的序列不是一个合法的闭合栅栏，那么输出文件只有一行，为"NOFENCE"(不包括引号)。
否则，输出是一个可见栅栏的列表。栅栏用两端的顶点表示，顶点的输出顺序以输入文件中的顺序为准。把栅栏按照最后一个点在输入文件中的顺序排序。如果两条栅栏的最后一个点是一样的，就以它们第一个点的顺序排序。