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 Mcerut.
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
Oricum am elimina 3 scanduri se poate ajunge
in linie dreapta de pe malul de sud pe cel de nord. In schimb,
putem elimina 2 scanduri (de exemplu cele colorate in rosu) astfel
incat tot sa nu existe un drum de la malul de sud la cel de nord.
In concluzie, 3 este numarul minim cerut.
student Filip Cristian
Buruiana
Facultatea de Automatica
si Calculatoare, Universitatea Politehnica Bucuresti
