figuri

Figuri

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

==Include(page="template/taskheader" task_id="figuri")==

Poveste ...

Se considera $N$ bucati dreptunghiulare de hartie colorata, care sunt asezate una dupa alta pe o foaie alba dreptunghiulara. Stim ca sistemul de coordonate are originea in centrul hartiei albe si ca axele sunt paralele cu laturile foii de hartie albe. Astfel, aceasta foaie alba poate fi impartita in patratele de latura unitate. Bucatile de hartie au marginile paralele cu foaia alba, si incap in intregime pe foaie. In final, daca ne uitam de sus, se vor vedea diferite figuri de diferite culori. Doua regiuni de aceeasi culoare fac parte din aceeasi figura, daca au cel putin un patratel care are cel putin un patratel vecin dintre cele $8$ ale sale, care face parte din cealalta regiune de aceeasi culoare.

h2. Cerinta

...

Sa se determine aria fiecarei figuri si numarul maxim de foi care se suprapun cel putin intr-un acelasi patratel comun.

h2. Restrictii

h2. Date de Intrare

...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...

Pe prima linie a fisierului $figuri.in$ se afla trei numere naturale {$a$}, $b$ si {$N$}, unde a reprezinta latimea foii de hartie (in figura de mai jos: numarul de patratele pe orizontala), $b$ reprezinta lungimea foii de hartie (numarul de patratele pe verticala), iar $N$ reprezinta numarul bucatilor de hartie colorata dreptunghiulara.
Urmatoarele $N$ linii contin fiecare cate $5$ numere intregi: $x{~1~}, y{~1~}, x{~2~}, y{~2~}$ si {$c$}, unde $x{~1~}$ si $y{~1~}$ reprezinta coordonatele coltului din stanga jos al dreptunghiului respectiv, x{~2~} si y{~2~} reprezinta coordonatele punctului de pe hartie unde va fi plasat coltul din dreapta sus al dreptunghiului, iar c reprezinta culoarea acestuia. Culoarea este un numar natural.
Ordinea liniilor din fisierul de intrare corespunde ordinii de asezare a dreptunghiurilor.
 
h2. Date de Iesire
 
Fisierul de iesire $figuri.out$ va contine cate o linie in care se descrie cate o figura "monocolora".
Pe fiecare linie se vor scrie doua numere intregi $c$ si {$d$}, unde c reprezinta codul culorii figurii care se descrie, iar $d$ reprezinta aria figurii respective.
Pe ultima linie a fisierului se va scrie un singur numar natural, reprezentand numarul maxim de bucati de hartie care se suprapun cel putin intr-un acelasi patratel comun. Vom numara si foaia alba data initial.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 1000$
* $1 ≤ a, b ≤ 200$
* $a$ si $b$ sunt numere pare
* $1 ≤ c ≤ 1000$
* culoarea alba este codificata cu $1$
* {$x{~1~} < x{~2~}$}, {$y{~1~} < y{~2~}$},
* $[-a/2] &le; x{~1~}, x{~2~} &le; [a/2]$
* $[-b/2] &le; y{~1~}, y{~2~} &le; [b/2]$
* Printre dreptunghiurile colorate putem avea si dreptunghiuri de culoare alba.
* Foaia alba initiala (parti din ea) poate face parte dintr-o figura.
* Numarul final de figuri nu depaseste {$1000$}.
* Figurile se vor descrie in fisierul de iesire in ordine crescatoare dupa codul culorii; daca exista mai multe astfel de figuri, ordinea va fi crescatoare dupa arie.

h2. Exemplu

| figuri.in | figuri.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. figuri.in |_. figuri.out |_. Figura |
| 20 12 6
-7 -5 -3 -1 4
-5 -3 5 3 2
-4 -2 -2 2 4
2 -2 3 -1 12
3 1 7 5 1
3 -3 4 -2 12
| 1 172
2 46
4 8
4 12
12 2
4
| !problema/figuri?figuri.gif! |

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

 
==Include(page="template/taskfooter" task_id="figuri")==
 
 

967