2852 「CEOI2012」印刷电路板

译自 CEOI 2012 Day1 T2「Printed Circuit Board」

印刷电路板，又称印制电路板，印刷线路板，常用英文缩写 PCB 或 PWB，是电子元件的支撑体，在这其中有金属导体作为连接电子元器件的线路。

贵公司想要生产一种将使用 PCB 制造的新电子设备。所需 PCB 的设计已部分完成，并且具有封闭多边形的形状。它由从 $1$ 到 $n$ 编号的 $n$ 个节点组成。节点 $u$ 和节点 $u + 1$ 通过直线线段连接，节点 $n$ 通过直线线段连接到节点 $1$。线段是不交叉的，即对于任何一对线段，如果它们有一个公共点，则该点必须是两个线段的端点，并且每个节点恰好是两个线段的端点。每个节点的位置由 $x$ 和 $y$ 坐标确定，原点 $(0, 0)$ 位于左下角。

你要编写一个程序，计算电路的所有节点，这些节点可以通过一条直线线段连接到原点，除了节点本身之外，该直线段与多边形没有共同点。

简化：

给出一个 $n$ 个顶点的简单多边形，对于每个顶点，假如它和原点连成的线段只在这个顶点处和多边形相交，就称为满足要求的顶点。你的任务是输出所有满足要求的顶点编号。

第一行一个正整数 $n$。

下面 $n$ 行每行两个不超过 $10^6$ 的正整数，依次表示每个顶点的坐标。顶点按照输入顺序用正整数 $1,2,\dots,n$ 编号，并且顶点保证按照顺时针或逆时针顺序给出。

第一行一个正整数 $m$，表示满足要求的顶点个数。

第二行 $m$ 个正整数，按照升序给出满足要求的顶点编号。

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$。

• 对于 $10\%$ 的数据，$n\le 10^3$。

如果输出的第一行正确，则可以获得该测试点 $40\%$ 的分数。