- Time limit: 4.00 s
- Memory limit: 512 MB
Tehtäväsi on selvittää jokaisesta seinämästä, minkä seinämän vaeltajat näkevät edessään. Toisin sanoen: kun seinämästä lähtee sen suuntainen suora eteenpäin, mikä on ensimmäinen seuraava seinämä, jonka jokin piste on tämän suoran yläpuolella?
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku $n$: seinämien kärkipisteiden määrä reitillä. Seinämät on numeroitu kokonaisluvuin $1,2,\ldots,n-1$.
Tämän jälkeen syötteessä on $n$ kokonaislukuparia: seinämän kärkipisteen x- ja y-koordinaatit. Kärkipisteet on annettu kasvavassa x-järjestyksessä.
Tuloste
Ohjelmasi tulee tulostaa $n-1$ kokonaislukua: jokaisesta seinämästä tieto, minkä seinämän vaeltajat näkevät. Jos he eivät näe mitään seinämää, tulosta 0.
Rajat
- $2 \le n \le 10^5$
- $0 \le x,y \le 10^9$
Syöte:
8
0 0
3 7
6 2
9 4
11 2
13 3
17 13
20 7
Tuloste:
0 3 6 5 6 0 0