|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|0.1 초||32 MB||98||11||7||9.722%|
According to Wikipedia, a printed circuit board, or PCB, is used to mechanically support and electrically connect electronic components using conductive pathways etched from copper sheets laminated onto a nonconductive substrate. Your company wants to produce a new electronic device that will be manufactured using a PCB. The design of the required PCB is partially ready, and has the shape of a closed polygon. It consists of N nodes numbered from 1 to N. Node u and node u+1 are connected by a straight line wire segment and node N is connected to node 1 by a straight line wire segment. Wire segments are non-crossing, that is for any pair of wire segments if they share a common point then this point must be an endpoint of both segments, and each node is the endpoint of exactly two segments. The location of each node is given by x- and y-coordinates, and the origin (0,0) is the lower left corner of the board.
You are to write a program that computes all nodes of the circuit that can be connected to the origin by a straight line wire segment that has no common point with the polygon other than the node itself.
The first line of the input contains one integer, N (1 ≤ N ≤ 200 000) the number of nodes of the circuit. Each of the next N lines contain two integers, x, y (0 < x, y ≤ 1 000 000) the x- and y-coordinates of a node. Nodes are numbered from 1 to N, the input line i+1 contains the coordinates of node i.
The first line of the output contains one integer M, the number of nodes that can be connected to the origin by a straight line wire segment so that this point is the only common point with any wire segment of the circuit. The second line contains these nodes separated by space in increasing order.
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