Pe un lac de latime H si lungime W metri se afla N scanduri cu latime neglijabila si lungime variabila. Scandurile se afla pe lac la pozitii cunoscute si, datorita lipsei curentilor, nu isi vor modifica pozitia niciodata. Pescarul Ion doreste sa plece cu o barca de pe malul de sud al lacului si sa ajunga pe malul de nord. Pescarul poate pleca din orice punct al malului de sud, si poate sa se deplaseze doar in linie dreapta, fara a trece prin zone ocupate de scanduri. Datorita acestor conditii, este posibil sa nu existe niciun drum valid intre cele doua maluri. Pescarul Ion isi da seama de acest lucru si isi propune sa elimine dinainte anumite scanduri de pe lac pentru a-si facilita trecerea. Cand obtine cel putin un drum, el nu mai elimina scanduri. Pentru ca nu este foarte inteligent, Ion poate efectua o munca inutila. De aceea are sens sa cunoastem efortul depus de pescar (egal cu numarul de scanduri eliminate) pe cazul cel mai defavorabil.
Cerinţă
Sa se determine numarul minim M astfel incat oricum am elimina M scanduri sa existe cel putin un drum in linie dreapta de la malul de sud la malul de nord.Date de intrare
Fişierul de intrare lac.in conţine pe prima linie doua numere naturale W si H, reprezentand dimensiunile lacului. A doua linie contine un numar natural N, reprezentand numarul de scanduri de pe lac. Fiecare dintre urmatoarele N linii, pana la sfarsitul fisierului, contine cate 3 numere naturale (y x1 x2), reprezentand o scandura situata la y metri de malul de sud, la x1 metri de malul de vest si avand lungimea x2-x1 metri. Numerele de pe aceeasi linie sunt separate prin spatiu.Date de ieşire
Fişierul de ieşire lac.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul minim M cerut.Restricţii
- 1 < N <= 100 000
- 5 < W, H <= 2 000 000 000
- Pentru orice scandura, 0 < y < H si 0 <= x1 < x2 <= W
- Scandurile vor fi sortate in fisierul de intrare crescator dupa x1
- Daca initial exista cel putin un drum de la malul de sud la cel de nord, raspunsul va fi 0
- Se garanteaza ca scandurile nu se vor intersecta in niciun punct
Exemple
|
lac.in |
lac.out |
Explicaţii |
|
8 6 5 3 0 4 5 1 7 2 2 3 4 3 5 3 7 8 |
3 |
|
|
student Filip Cristian Buruiana |
|
Facultatea de Automatica si Calculatoare, Universitatea Politehnica Bucuresti |