10341 - 闭合的栅栏

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

每一对相邻的顶点都是一条栅栏。因此共有N条栅栏 (定义xN+1=x1, yN+1=y1)。

这里有一个栅栏的例子和一个点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)看见的。

第一行: N, 表示闭合栅栏的顶点数。 第二行: 两个整数x和y，表示观测者的位置。两个整数都是16位的。
第3到N+2行: 每行一对整数(x,y)表示对应闭合栅栏的第k个顶点的坐标。坐标以逆时针顺序给出。整数绝对值不超过1000。

如果给出的序列不是一个合法的闭合栅栏，那么输出文件只有一行，为"NOFENCE"(不包括引号)。

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

Closed Fences

A closed fence in the plane is a set of non-crossing, connected line segments with N corners (3 < N < 200). The corners or vertices are each distinct and are listed in counter-clockwise order in an array {xi, yi}, i in (1..N).

Every pair of adjacent vertices defines a side of the fence. Thus {xi yi xi+1 yi+1} is a side of the fence for all i in (1..N). For our purposes, N+1 = 1, so that the first and last vertices making the fence closed.

Here is a typical closed fence and a point x,y:

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

Write a program which will do the following:

Test an ordered list of vertices {xi,yi}, i in (1..N) to see if the array is a valid fence. Find the set of fence sides that a person (with no height) who is standing in the plane at position (x,y) can "see" when looking at the fence. The location x,y may fall anywhere not on the fence. A fence side can be seen if there exists a ray that connects (x,y) and any point on the side, and the ray does not intersect any other side of the fence. A side that is parallel to the line of sight is not considered visible. In the figure, above the segments x3,y3-x4,y4; x5,y5-x6,y6; and x6-y6-x1,y1 are visible or partially visible from x,y.

PROGRAM NAME: fence4 INPUT FORMAT Line 1: N, the number of corners in the fence
Line 2: Two space-separated integers, x and y, that are the location of the observer. Both integers will fit into 16 bits. Line 3-N+2: A pair of space-separated integers denoting the X,Y location of the corner. The pairs are given in counterclockwise order. Both integers are no larger than 1000 in magnitude.

SAMPLE INPUT (file fence4.in) 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

OUTPUT FORMAT If the sequence is not a valid fence, the output is a single line containing the word "NOFENCE".

Otherwise, the output is a listing of visible fence segments, one per line, shown as four space-separated integers that represent the two corners. Express the points in the segment by showing first the point that is earlier in the input, then the point that is later. Sort the segments for output by examining the last point and showing first those points that are earlier in the input. Use the same rule on the first of the two points in case of ties.

SAMPLE OUTPUT (file fence4.out) 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