P6237 [CEOI 2012] Printed Circuit Board

题目描述

给出一个 $n$ 个顶点的简单多边形,对于每个顶点,假如它和原点连成的线段只在这个顶点处和多边形相交,就称为满足要求的顶点。你的任务是输出所有满足要求的顶点编号。 ![](https://cdn.luogu.com.cn/upload/image_hosting/beasw2yx.png)

输入格式

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

输出格式

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

说明/提示

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