Comet OJ

C0357 [USACO]闭合的栅栏

内存限制：256 MB 时间限制：1000 ms

题目描述

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

每一对相邻的顶点都是一条栅栏。因此共有 $N$ 条栅栏（定义 $x_{N+1}=x_1, y_{N+1}=y_1$）。

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

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

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

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

只有当存在从 $(x,y)$ 发射的一条射线第一个穿过栅栏 $i$ 时，栅栏 $i$ 是可以被看见的。如果栅栏是平行于目光的，它并不认为是可以看见的。在上面的例子里，线段 $[x_3,y_3]-[x_4,y_4], [x_5,y_5]-[x_6,y_6], [x_6-y_6]-[x_1,y_1]$ 是可以被 $(x,y)$ 看见的。

输入格式

第一行：$N$，表示闭合栅栏的顶点数。

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

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

输出

如果给出的序列不是一个合法的闭合栅栏，那么输出只需要输出 “NOFENCE”。（实际上这种情况不会发生）

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

样例

样例输入 1

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

样例输出 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

提示