Aed

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

요약

단순 닫힌 다각형과 외부의 한 점이 주어질 때, 그 점에서 보이는 다각형의 변을 세어 오름차순으로 출력한다.

난이도: 보통10점 중 7점
유형: 기하, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

Onu Uno ehitab karjamaa ümber aeda. Aed on $N$ sirglõigust koosnev kinnine murdjoon. See tähendab, et iga järgmine lõik algab sealt, kus eelmine lõppes, ja viimane lõik lõpeb esimese lõigu alguspunktis. Lõigud on nummerdatud $1 \ldots N$ vastupäeva. Võib eeldada, et aialõigud omavahel ei lõiku ega puutu (välja arvatud järjestikuste lõikude ühised otspunktid).

Kui Onu Uno on aia valmis saanud, tahab ta selle üle vaadata. Kirjuta programm, mis saab Onu Uno asukoha ja leiab, milliseid aialõike ta seal seistes näeb. Onu Uno võib seista nii aia sees kui ka sellest väljas, kuid mitte ühegi aialõiguga samal sirgel.

Onu Uno näeb aialõiku, kui leidub tema asukohta ja aialõigu mingit punkti ühendav sirglõik, mis ei lõika ega puutu ühtegi teist aialõiku. (Teisisõnu, aialõigu Unole nähtav osa peab olema nullist suurema pikkusega.)

입력

Tekstifaili esimesel real on aialõikude arv $N$ ( $3 \le N \le 1\\,000$ ). Teisel real on kaks tühikuga eraldatud täisarvu: Onu Uno asukoha koordinaadid $X$ ja $Y$ . Järgmisel $N$ real on igaühel kaks tühikuga eraldatud täisarvu: real $i + 2$ on aialõigu number $i$ alguspunkti koordinaadid $X\_i$ ja $Y\_i$ . Kõik koordinaadid on täisarvud absoluutväärtusega kuni $10^5$ .

출력

Tekstifaili esimesele reale väljastada üks täisarv: Onu Unole nähtavate aialõikude arv $M$ . Teisele reale väljastada $M$ tühikutega eraldatud täisarvu: nähtavate aialõikude numbrid kasvavas järjekorras.

예제3

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