#P2856. [ceoi2012]Printed Circuit Board

    ID: 1968 传统题 1000ms 512MiB 尝试: 138 已通过: 18 难度: 8 上传者: 标签>CF2500提高+/省选-叉积自定义排序规则离散化普通线段树有理数精确运算

[ceoi2012]Printed Circuit Board

题目描述

给出一个 nn 个顶点的简单多边形,对于每个顶点,假如它和原点连成的线段只在这个顶点处和多边形相交,就称为满足要求的顶点。

你的任务是输出所有满足要求的顶点编号。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个数 xi,yix_i,y_i 表示第 ii 个点的坐标。

顶点按照输入顺序用正整数 11 到 nn 编号,并且顶点保证按照顺时针或逆时针顺序给出。

输出格式

第一行一个整数 mm。

第二行 mm 个整数,按升序输出满足要求的顶点编号。

11
7 6
4 4
3 2
1 3
9 9 
13 4
8 1
6 4
9 5
8 3
11 5
3
3 4 7

样例解释

样例所表示的多边形如下图:

![](file://pic1.jpg)

数据规模与约定

对于 100%100\%​ 的数据,1≤xi,yi≤1061\leq x_i,y_i \leq 10^6​,1≤n≤2×1051\leq n\leq 2\times 10^5。