만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

울타리

시간 제한1초메모리 제한1024 MB

요약
닫힌 울타리 다각형과 관찰자의 좌표가 주어질 때, 관찰자가 길이가 0보다 큰 부분을 볼 수 있는 울타리 선분의 번호를 구합니다.
난이도

보통10점 중 6점

유형
기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

Onu Uno는 농장 둘레에 울타리를 세우고 있다. 울타리는 NN개의 직선 선분으로 이루어진 닫힌 꺾은선이다. 각 선분은 앞 선분이 끝나는 점에서 시작하고, 마지막 선분은 첫 번째 선분의 시작점에서 끝난다. 선분은 반시계 방향으로 1…N1 \ldots N번 번호가 매겨져 있다. 연속한 선분끼리 만나는 공통 끝점을 제외하면 울타리 선분들끼리 교차하거나 닿지 않는다.

울타리를 다 세운 뒤 Onu Uno는 이를 둘러보려 한다. Onu Uno의 위치를 입력받아, 그 자리에서 보이는 울타리 선분을 찾는 프로그램을 작성하라. Onu Uno는 울타리 안이나 밖에 설 수 있지만, 어떤 울타리 선분과도 같은 직선 위에 설 수는 없다.

Onu Uno가 어떤 선분을 볼 수 있다는 것은, 그의 위치에서 그 선분 위의 한 점까지 잇는 직선이 있고 그 직선이 다른 울타리 선분과 교차하거나 닿지 않는다는 뜻이다. 즉 선분이 보이는 부분의 길이가 0보다 커야 한다.

입력

첫 줄에 울타리 선분의 개수 NN(3≤N≤1 0003 \le N \le 1\,000)이 주어진다. 둘째 줄에 Onu Uno의 좌표 XX와 YY가 공백으로 구분되어 주어진다. 이어지는 NN개 줄 중 i+2i + 2번째 줄에는 선분 ii의 시작점 좌표 XiX_i와 YiY_i가 공백으로 구분되어 주어진다. 모든 좌표는 절댓값이 10510^5 이하인 정수이다.

출력

첫 줄에 Onu Uno가 볼 수 있는 선분의 개수 MM을 출력한다. 둘째 줄에는 보이는 선분의 번호를 오름차순으로 공백으로 구분하여 출력한다.

예제3

  1. 예제 1

    입력
    4
    2 2
    1 1
    3 1
    3 3
    1 3
    
    예상 출력
    4
    1 2 3 4
    
  2. 예제 2

    입력
    4
    5 6
    1 1
    4 1
    4 4
    1 4
    
    예상 출력
    2
    2 3
    
  3. 예제 3

    입력
    5
    5 6
    1 1
    5 1
    2 3
    5 5
    1 5
    
    예상 출력
    1
    4