| Fișierul intrare/ieșire | laser.in, laser.out | Sursă | Concurs Nerdvana |
|---|---|---|---|
| Autor | CodeChef | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 0.4 sec | Limită de memorie | 524288 KB |
| Scorul tău | N/A | Dificultate |
   2.25
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Laser (clasele 9-12)
Această problemă este adaptată după Lasers Everywhere
O linie poligonală este descrisă prin n puncte în plan, (xP1, yP1) ... (xPn, yPn), care determină n – 1 segmente. Coordonatele x ale punctelor sînt strict crescătoare. În plan există q lasere. Laserul i (1 ≤ i ≤ q) este amplasat la coordonatele (xLi, yLi) și emite o rază spre dreapta (paralelă cu axa Ox), pînă la infinit.
Determinați cîte segmente din linia poligonală intersectează fiecare rază. Considerăm că raza laserului i intersectează un segment dacă orice punct al razei (inclusiv sursa (xLi, yLi)) atinge orice punct al segmentului (inclusiv extremitățile).
Date de intrare
Fișierul de intrare laser.in conține pe prima linie numerele n și q. Următoarele n linii descriu punctele, linia i conținînd două numere xPi yPi. Următoarele q linii descriu laserele, linia i conținînd două numere xLi yLi.
Date de ieșire
În fișierul de ieșire laser.out afișați numărul de segmente intersectate de raza fiecărui laser, în ordinea de la intrare.
Restricții
- 1 ≤ n, q ≤ 200000
- 1 ≤ xPi, yPi, xLi, yLi ≤ 500000 pentru orice i.
- Toate coordonatele sînt întregi.
- Testele nu sînt grupate.
| subtask | puncte | restricții |
|---|---|---|
| 1 | 30 | n, q ≤ 4000 |
| 2 | 50 | n, q ≤ 100000 |
| 3 | 20 | Fără restricții suplimentare. |
Exemplu
| laser.in | laser.out |
|---|---|
| 5 4 1 2 2 5 3 3 7 1 9 4 4 2 3 3 1 6 10 1 |
2 3 0 0 |
Explicație
