P15510 [CEOI 2014] 法贡森林 / The Forest of Fangorn

翻译来自 [Libre OJ](https://loj.ac/p/3287)。

小 G 一进到法贡森林就感受到不对劲，他感觉这里的树有问题。因此，小 G 想去往森林边缘的一个营地。然而因为他时刻被这种不安感围绕着，他不得不检查每一棵树。幸运的是，他们家族的视力很好，能够看清任意方向无限远的树木。 法贡森林是一个各边平行于坐标轴的矩形 $F$，左下角和右上角分别为 $(0,~0)$ 和 $(w,~h)$。森林里共有 $N$ 棵树，均位于这个矩形的内部。此外，有 $C$ 个营地 $1\ldots C$ 位于矩形的边上。所有的树只在竖直方向生长，因此可以视为一个点。因此，小 G 能看到一棵树当且仅当他与这棵树的连线上没有其他树。注意小 G 并不能爬树。 在任意一个营地，小 G 都可以看到所有的树。起始时，它位于矩形内部一个没有树的位置，并且在这里他能看到所有的树和营地。因为法贡森林历史悠久，保证不存在三棵树共线。 我们称小 G 能平安到达营地 $c$ 当且仅当从起始点开始存在一条路径 $\gamma$ 使得在 $\gamma$ 上的任意点能看到所有的树。你的任务是编写一个程序算出小 G 能平安到达的所有点。

第一行两个空格分隔的整数 $w$ 和 $h$，表示矩形 $F$ 的大小。 第二行两个空格分隔的整数 $x_G,~y_G$，表示小 G 的起始位置。 第三行一个整数 $C$，表示营地的数目。 接下来 $C$ 行每行两个空格分隔的整数 $x_i,~y_i$，表示营地 $i$ 的坐标。 接下来一行一个整数 $N$，表示树木的数目。 接下来 $N$ 行每行两个空格分隔的整数 $x$ 和 $y$，表示一棵树木的坐标。保证树木的坐标互不相同。

第一行一个整数 $m$，表示小 G 能安全到达的营地数。 如果 $m\neq 0$，下一行升序输出可到达营地的编号。

【样例 $1$ 解释】 一条满足题面条件的路径如下图所示：  注意在这个过程中小 G 可以离开森林，但不在森林里时他还是想要能看到所有树，不然在这个样例中第二个营地也将可以安全到达。 【数据范围】 对于 $100\%$ 的数据，有 $3\le N\le 2000,~1\le C\le 10000,~0< w,~h\le 10^9$。 |子任务|分值|额外限制| |:-:|:-:|:-:| |$1$|$30$|$N\le 70,~C\le 5$| |$2$|$20$|树木形成了凸多边形的一角，$N\le 200,~C\le 5$| |$3$|$30$|$C\le 5$| |$4$|$20$|无特殊限制|