시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
1.0 초 512 MB 2 1 (50%) 1
문제
Wikipedia에 따르면, 인쇄 회로 기판(PCB, Printed Circuit Board)는 기계적 지원에 사용되고 동기판에서 비전도 "기판"으로 습식 식각한 전도선이나, 신호 선을 사용하여 전기적으로 전자 부품을 연결한다.
Drawing
당신의 회사는 PCB를 사용한 새로운 전자기기를 만들려 한다. 그 PCB는 N개의 꼭지점을 가진 폐다각형 모양으로 생겼다. 각 꼭지점에 1부터 N까지의 숫자를 붙였을 때, 꼭지점 u와 u+1은 직선으로 연결되어 있고 꼭지점 N과 1도 직선으로 연결되어 있다. 꼭지점을 잇는 선분들은 서로 교차하지 않는다. 즉, 임의의 두 선분이 겹치는 부분이 있다면 그 부분이 두 선분 각각의 끝 점인 경우 뿐이다. 각 꼭지점의 위치는 (x,y) 좌표로 주어지며 원점 (0,0)는 PCB의 가장 왼쪽 아래를 나타낸다. PCB 폐다각형의 꼭지점들 중에서, 그 꼭지점과 원점 (0,0)을 직선으로 이었을 때 그 직선이 PCB 폐다각형과 만나지도, 겹치지도 않는 꼭지점들을 구하라. (즉, 그 직선과 PCB 폐다각형이 겹치는 유일한 점은 그 꼭지점이 되어야 한다.)
입력
표준 입력에서 다음의 입력을 읽는다. 첫 번째 줄에는 PCB 폐다각형의 꼭지점 수를 나타내는 정수 N(1 $\leq$ N $\leq$ 200,000)이 주어진다. 다음 N개 각각의 줄에는 꼭지점 i의 위치를 (x,y) 좌표로 나타내는 두 정수 x, y(0 $<$ x, y $\leq$ 1,000,000)가 주어진다. 꼭지점에는 1부터 N까지의 번호가 붙어 있으며, 입력의 i+1번째 줄이 꼭지점 i의 좌표를 나타낸다.
출력
표준 출력으로 다음을 출력한다. 첫 번째 줄에 원점 (0,0)에 이은 직선이 PCB 폐다각형과 만나거나 겹치지 않는 꼭지점들의 개수를 출력한다. 두 번째 줄에는 그러한 꼭지점들의 번호를 빈 칸을 사이에 두고 오름차순으로 출력한다.
힌트
다음 항목들에 대하여 부분점수를 받을 수 있다. - 테스트 케이스의 10%는 N이 1000을 넘지 않는다. - 출력의 첫 번째 줄(개수)만 맞은 경우, 전체 점수의 40%를 받을 수 있다. #### 입력 예시 ``` 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 ```