Aed | 프로그래밍의 벗 PivotOJ
PivotOJ

Aed

시간 제한: 1000ms메모리 제한: 1024MB출처: EIO 2019-20 sel2BOJ 29931

문제

Onu Uno ehitab karjamaa ümber aeda. Aed on NN 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 1N1 \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 NN (3N10003 \le N \le 1\,000). Teisel real on kaks tühikuga eraldatud täisarvu: Onu Uno asukoha koordinaadid XX ja YY. Järgmisel NN real on igaühel kaks tühikuga eraldatud täisarvu: real i+2i + 2 on aialõigu number ii alguspunkti koordinaadid XiX_i ja YiY_i. Kõik koordinaadid on täisarvud absoluutväärtusega kuni 10510^5.

출력

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

예제

예제 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
코드를 제출하려면 로그인하세요.