프로그램 명: ceoi_circuit
제한시간: 1 초
[문제요약] 폐 곡선의 각 점의 좌표가 주어질 때 원점에서 각 꼭지점으로 선을 연결할 때 폐곡선을 건들지 않는 점의 개수와
점을 구하는 문제.
점을 출력할 때 오름차순으로 출력
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.
Task
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 ≤ 100 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
출처:ceoi 2012
[질/답]
[제출 현황]
[푼 후(0)]