Fişierul intrare/ieşire:obstacole.in, obstacole.outSursăJunior Challenge 2019
AutorVlad TurcumanAdăugată deJuniorChallenge2019Junior Challenge 2019 JuniorChallenge2019
Timp execuţie pe test0.75 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Obstacole

Se dau N segmente în plan, neorizontale şi neverticale care nu se intersectează în niciun punct. Aceste segmente se comportă ca nişte obstacole.

Fie M baloane cu aer cald care merg în sus ( x-ul rămâne la fel, y creşte). Dacă un balon ajunge la un obstacol, balonul va merge de-a lungul obstacolului, în direcţia în care y creşte. Când balonul a ajuns la capătul obstacolului, el va continua ca înainte să meargă în sus ( x-ul va rămâne neschimbat până la următorul obstacol pe care îl întălneşte).

Pentru fiecare dintre cele M baloane se cere să se afişeze x-ul pe care o să îl aibă după trece de toate obstacolele pe care le va întâlni.

Atenţie! Dacă un balon, mergând în sus, ajunge la capătul unui obstacol, atunci balonul va urma obstacolul. (vezi balonul 1 0 din exemplu)
Atenţie! Baloanele pot începe şi de pe obstacole. În acest caz, ele vor merge pe obstacol. (vezi balonul 13 7 din exemplu)

Date de intrare

Fişierul de intrare obstacole.in se va găsi pe prima linie N şi M. Pe următoarele N linii se vor găsi câte 4 numere x1, y1, x2, y2 reprezentând coordonatele punctelor unui segment. Pe următoarele M linii se vor găsi cate 2 numere x, y reprezentând coordonatele de plecare ale balonului.

Date de ieşire

În fişierul de ieşire obstacole.out se vor găsi M numere, câte unul pe linie, fiecare semnificând x-ul la care o să ajungă balonul corespondent.

Restricţii

  • 1 ≤ N, M ≤ 105
  • 0 ≤ x, y, x1, y1, x2, y2 ≤ 109 + 104
  • Pentru 20% din punctaj, N ≤ 100 şi M ≤ 100.
  • Pentru 50% din punctaj, N ≤ 1000 şi M ≤ 1000.

Exemplu

obstacole.inobstacole.out
6 7
1 1 15 4
1 4 7 8
8 7 9 8
2 9 6 11
6 10 8 8
11 9 13 7
1 3
1 0
3 3
4 8
8 5
11 5
13 7
6
15
6
6
9
11
11

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?