6856 - 3.4.1 Closed Fences 闭合的栅栏
一个闭合的栅栏是平面上的一些不相交的首尾相连的线段形成的多边形,有 N个角(顶点) (3 < N < 200). 顶点不重合,它以逆时针方式以数组{xi, yi}给出(i=1,2,...,N).
每一对相邻的顶点都是一条栅栏.因此共有 N条栅栏 (定义 xN+1=x1, yN+1=y1). 这里有一个栅栏的例子和一个点 x,y:
请编写一个程序实现下面的任务:
检查输入的顶点列表{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"(不包括引号). 否则,输出是一个可见栅栏的列表.栅栏用两端的顶点表示,顶点的输出顺序以输入文件中的顺序为准. 把栅栏按照最后一个点在输入文件中的顺序排序.如果两条栅栏的最后一个点是一样的,就以它们 第一个点的顺序排序.
样例
输入
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
输出
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
来源
USACO