울타리
시간 제한1초메모리 제한1024 MB
닫힌 울타리 다각형과 관찰자의 좌표가 주어질 때, 관찰자가 길이가 0보다 큰 부분을 볼 수 있는 울타리 선분의 번호를 구합니다.
문제
Onu Uno는 농장 둘레에 울타리를 세우고 있다. 울타리는 개의 직선 선분으로 이루어진 닫힌 꺾은선이다. 각 선분은 앞 선분이 끝나는 점에서 시작하고, 마지막 선분은 첫 번째 선분의 시작점에서 끝난다. 선분은 반시계 방향으로 번 번호가 매겨져 있다. 연속한 선분끼리 만나는 공통 끝점을 제외하면 울타리 선분들끼리 교차하거나 닿지 않는다.
울타리를 다 세운 뒤 Onu Uno는 이를 둘러보려 한다. Onu Uno의 위치를 입력받아, 그 자리에서 보이는 울타리 선분을 찾는 프로그램을 작성하라. Onu Uno는 울타리 안이나 밖에 설 수 있지만, 어떤 울타리 선분과도 같은 직선 위에 설 수는 없다.
Onu Uno가 어떤 선분을 볼 수 있다는 것은, 그의 위치에서 그 선분 위의 한 점까지 잇는 직선이 있고 그 직선이 다른 울타리 선분과 교차하거나 닿지 않는다는 뜻이다. 즉 선분이 보이는 부분의 길이가 0보다 커야 한다.
입력
첫 줄에 울타리 선분의 개수 ()이 주어진다. 둘째 줄에 Onu Uno의 좌표 와 가 공백으로 구분되어 주어진다. 이어지는 개 줄 중 번째 줄에는 선분 의 시작점 좌표 와 가 공백으로 구분되어 주어진다. 모든 좌표는 절댓값이 이하인 정수이다.
출력
첫 줄에 Onu Uno가 볼 수 있는 선분의 개수 을 출력한다. 둘째 줄에는 보이는 선분의 번호를 오름차순으로 공백으로 구분하여 출력한다.