Cerința
Se consideră un număr N
natural fixat. Se construiește mulțimea A
care conține N x N
puncte din cadranul 1, de coordonate numere naturale:
(1, 1), (1, 2), …, (1, N),
(2, 1), (2, 2), …, (2, N),
………………………………
(N, 1), (N, 2), …, (N, N).
Se dau T
segmente S1, S2, …., ST
, fiecare dintre aceste segmente având extremitățile două puncte din A
.
Numim segment simplu, un segment Si (1<=i<=T)
cu proprietatea că Si
nu mai conține alte puncte din A
, în afară de extremități.
Din șirul T
de segmente dat, se extrag segmentele simple SS1, SS2, …, SSk
, în aceeași ordine în care erau în șirul de segmente inițial.
Pe baza lungimilor segmentelor extrase se construiește SL
= șirul lungimilor acestor segmente L1, L2, …, Lk.
Se cere să se determine lungimea maximă L
a unui subșir crescător a șirului SL
.
Date de intrare
Programul citește din fișierul masterpiece002.in
mai multe linii, fiecare dintre aceste linii conținând câte patru numere X1, Y1, X2, Y2
separate prin spațiu. Fiecare linie reprezintă un segment de extremități (X1, Y1)
și (X2, Y2)
.
Date de ieșire
Programul va scrie în fișierul masterpiece002.out
un singur număr reprezentând numărul L
, cu semnificația din enunț.
Restricții și precizări
N ≤ 1000
T ≤ 505.050
Exemplu:
masterpiece002.in
2 2 3 3 1 1 4 1 2 1 4 3 1 2 1 3 1 1 4 2 4 1 4 3
masterpiece002.out
2
Explicație
Se dau 6
segmente.
(2,2) – (3,3)
(1,1) – (4,1)
(2,1) – (4,3)
(1,2) – (1,3)
(1,1) – (4,2)
(4,1) – (4,3)
În figura de mai sus:
Segmentele verzi sunt segmente simple.
Segmentul portocalii nu sunt segmente simple.
Pentru exemplul din figură, șirul SS
va conține segmentele: {SS1 = (2,2) – (3,3), SS2 = (1,2) – (1,3), SS3 = (1,1) – (4,2)}
Segmentul (2,2) – (3,3)
are lungime 1.4142
Segmentul (1,2) – (1,3)
are lungime 1.000
Segmentul (1,1) – (4,2)
are lungime 3.1622
Pentru exemplul din figură SL = {1.4141, 1.000, 3.1622}
Rezultatul va fi 2
. Lungimea maximă a unui subșir crescător al șirului SL
este 2
.
Această lungime se poate obține considerând astfel:
- Se aleg segmentele SS1 = (2,2) - (3,3)
și SS3 = (1,1) - (4,2)
sau
- Se aleg segmentele SS2 = (1,2) - (1,3)
și SS3 = (1,1) - (4,2)
.