P15535 [CEOI 2005] Electric Fence

**在洛谷上，目前只支持以 C++ 语言提交并评测，且不建议使用 C++14 (GCC 9) 提交。** 在洛谷上提交时，你不需要 `include` 题目中所说的库并进行任何配置，只需要在代码开头加入如下代码以声明题目中的函数： ```cpp extern "C" long GetN(void); extern "C" int Drift(long x, long y, long z); extern "C" void Answer(long left, long right); ```

农夫 G 有一块很大的牧场，被一圈电围栏包围。围栏由围栏柱和直线的电线段组成，每一段电线连接两根相邻的柱子。围栏显然不会自相交，即没有任何一段电线会与另一段电线相交。农夫 G 得知将要修建一条新的直线路径，它可能会穿过他的牧场。他来到牧场后注意到，这条路的两个端点已经由两根柱子标记出来，分别是 $a$ 和 $b$。他意识到，道路所在的直线会把他的牧场内部区域分割成若干个互不相交的区域。 农夫 G 想确定道路两侧最终会形成多少个区域。他发现没有任何围栏柱位于道路所在的直线上。此外，如果某一段电线与道路所在的直线相交，那么交点一定落在端点 $a$ 与 $b$ 之间。 不幸的是，农夫 G 没有测量两根柱子间距离的工具。他只能观察柱子的相对方向关系：也就是说，他可以走到任意柱子 $p$（注意道路端点也是柱子），面向柱子 $q$ 时，他能判断第三个柱子 $r$ 位于他的左侧、右侧，还是三点共线。幸运的是，农夫 G 带着他的笔记本电脑（和往常一样），因此即使是复杂计算他也能完成。  ### 任务 你需要编写一个程序，用来计算：由于规划中的道路把牧场内部区域切分开之后，道路左侧与右侧分别会形成多少个互不相交的区域。 ### 库 为了进行查询，你会得到一个库 $\tt lookup$，其中有三个操作： - $\tt GetN$，在开始时调用一次，不带参数；它返回 $N$，即围栏柱的数量。第一次调用 $\tt Drift$ 之前必须先调用 $\tt GetN$。 - $\tt Drift$，用三个柱子的编号作为参数调用。$\tt Drift(x,y,z)$：当从 $x$ 朝 $y$ 看时，如果柱子 $z$ 位于左侧则返回 $1$，若位于右侧则返回 $-1$，若三点共线则返回 $0$。围栏柱的编号为 $1$ 到 $N$，道路端点 $a$ 和 $b$ 的编号分别为 $N+1$ 与 $N+2$。围栏的电线段连接编号为 $i$ 与 $(i \bmod N)+1$ 的围栏柱。若 $\tt Drift$ 的三个参数中至少有两个相同，$\tt Drift$ 也会返回 $0$。 - $\tt Answer$，在最后调用一次；它汇报答案并正确终止程序执行。$\tt Answer$ 有两个整数参数：第一个与第二个参数必须分别是道路左侧与右侧的互不相交区域数量。（若围栏柱 $p$ 位于道路左侧或右侧，则 $\tt Drift(a,b,p)$ 分别返回 $1$ 或 $-1$。） 你的程序不允许读写文件。输入与输出由库来处理。 **Pascal 程序员操作指南**: 在你的源代码中包含导入语句 ```pascal uses lookup; ``` **C/C++ 程序员操作指南**: 在你的源代码中使用指令 ```cpp #include "lookup.h" ``` 在题目目录中创建一个工程文件，把 `fence.c`（`fence.cpp`）、`lookup.h` 和 `lookup.o` 加入该工程，然后编译和/或构建你的程序。（使用 Dev-C++ IDE 时，选择 Project/Project Options/Files 菜单，选中文件 `lookup.o`，取消 “include in compilation” 并设置 “include in linking”。） 命令行编译： ```bash gcc/g++ -O2 –static –o fence fence.c lookup.o -lm ``` ### 测试 你会得到一套工具包（见题目附件），其中包含适用于 WinXP 与 Linux 的库。你可以下载这个 zip 压缩包，把对应的库文件复制到你的题目目录中。 工具包包含一个测试生成器 $\tt testgener$，用于生成文件 `fence.in`，其中包含合法的随机样例输入。$\tt testgener$ 需要一个整数参数 $N$，表示围栏柱的大致数量。如果 $N < 300$，那么 $\tt testgener$ 还会生成一个 postscript 文件 `fence.ps` 来可视化围栏布局（你可以用 gsview 或其他 postscript 查看器查看）。生成的测试数据在偶数与奇数的 $N$ 上差异很大；你可以试试看！警告：$\tt testgener$ 不能生成所有可能的输入。 由 $\tt Answer$ 提交的解会被写入文件 `fence.out`。 你也可以通过创建一个文本文件 `fence.in` 来制作自己的输入。第一行必须包含四个整数，表示道路两个端点的坐标。第二行必须包含 $N$，即围栏柱的数量。接下来的 $N$ 行每行必须包含一对整数 $x\ y$（$-20\ 000 \le x, y \le 20\ 000$）；第 $i+2$ 行中的这一对整数定义了编号为 $i$ 的围栏柱的坐标。

无

无

### 限制 - 对于围栏柱数量 $N$，有 $3 \le N \le 100\ 000$。 - FreePascal 的库文件名：WinXP 下为 `lookup.ppu` 和 `lookup.o`，Linux 下为 `lookup.o`。 - Pascal 函数声明： ```pascal function GetN: longint; function Drift(x, y, z: longint): integer; procedure Answer(x, y: longint); ``` - C/C++ 的库文件名：`lookup.h` 和 `lookup.o`。 - C/C++ 函数声明： ```cpp long GetN(void); int Drift(long x, long y, long z); void Answer(long left, long right); ```