Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-04-12 14:10:22.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cuiburi.in, cuiburi.outSursăONI 2010 - Baraj
AutorMarius DumitranAdăugată deandrei-alphaAndrei-Bogdan Antonescu •andrei-alpha
Timp execuţie pe test0.25 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cuiburi

În ţara Nicăieri există N cuiburi. Cuiburile sunt reprezentate în plan fie prin cercuri, fie prin dreptunghiuri cu laturile paralele cu axele. Pentru două cuiburi A şi B spunem că A se cuibăreşte în B dacă orice punct din interiorul sau de pe marginea cuibului A se află în interiorul sau pe marginea cuibului B. Numim o cuibăreală o submulţime de cuiburi A1, A2, A3, ..., Ak, în care Ai este cuibărit în Ai+1, pentru fiecare 1 <= i < k.

Cerinta

Pentru cele N cuiburi date, scrieţi un program care găseşte cardinalul maxim al unei cuibăreli. Cardinalul unei cuibăreli este egal cu numărul de cuiburi care alcătuiesc cuibăreala.

Date de intrare

Pe prima linie a fişierului de intrare cuiburi.in se găseşte numărul natural N, reprezentând numărul de cuiburi. Pe următoarele N linii vor fi descrise cele N cuiburi astfel: primul număr t de pe fiecare linie va fi 0 sau 1. Dacă t este 0, atunci pe linie se vor mai găsi 4 numere naturale lx ly rx ry, separate prin câte un spaţiu. Perechea (lx, ly) reprezintă colţul stânga-jos al dreptunghiului, iar perechea (rx, ry) colţul dreapta sus al dreptunghiului. Dacă t este 1, atunci pe linie se mai găsesc încă 3 numere naturale x y r, unde (x, y) reprezintă centrul cercului, iar r raza cercului.

Date de ieşire

În fişierul de ieşire cuiburi.out va conţine un singur număr natural reprezentând cardinalul maxim al unei cuibăreli.

Restricţii

  • Cuiburile se pot intersecta.
  • 1 ≤ N ≤ 2000
  • lx ≤ rx
  • ly ≤ ry
  • Pentru 20% din teste, N ≤ 20
  • Pentru 30% din teste, toate cuiburile vor fi dreptunghiuri
  • Pentru 30% din teste, toate cuiburile vor fi cercuri
  • Coordonatele şi razele sunt numere naturale mai mici sau egale cu 30 000

Exemplu

cuiburi.incuiburi.out
8
0 1 1 5 5
0 6 1 8 2
1 9 9 2
0 3 1 5 3
0 2 2 4 4
1 3 3 1
0 2 2 4 4
0 9 9 11 15
4

Explicaţie

Cuibăreala de cardinal maxim este alcătuită din cuiburile cu indicii 6, 5, 7, 1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?