프로그램 명: 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.

입력

출력

입출력 예

입력

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)]
[ 채 점 ] [홈으로]  [뒤 로]