cuiburi

Cuiburi

== include(page="template/taskheader" task_id="cuiburi") ==

Poveste şi cerinţă...

Î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 $A{~1~}, A{~2~}, A{~3~}, ..., A{~k~}$, în care $A{~i~}$ este cuibărit în $A{~i+1~}$, pentru fiecare $1 <= i < k$.
 
h2. 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.

h2. Date de intrare

Fişierul de intrare $cuiburi.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $cuiburi.out$ ...

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

h2. 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$

h2. Exemplu
table(example). |_. cuiburi.in |_. cuiburi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|
h3. Explicaţie

...

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

== include(page="template/taskfooter" task_id="cuiburi") ==

4795