==Include(page="template/taskheader" task_id="figuri")==
==Include(page="template/raw")==
Figuri
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. Date de Intrare
. 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 -L- n -L- 1000;
. 1 -L- a, b -L- 200; a si b sunt numere pare;
. 1 -L- c -L- 1000, culoarea alba este codificata cu 1;
. x[1] < x[2], y[1] < y[2],
. [-a/2] -L- x[1], x[2] -L- [a/2],
. [-b/2] -L- y[1], y[2] -L- [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
20 12 6 1 172
-7 -5 -3 -1 4 2 46
-5 -3 5 3 2 4 8
-4 -2 -2 2 4 4 12
2 -2 3 -1 12 12 2
3 1 7 5 1 4
3 -3 4 -2 12
==Include(page="template/taskheader" task_id="figuri")==
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. Date de Intrare
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] ≤ x{~1~}, x{~2~} ≤ [a/2]$
* $[-b/2] ≤ y{~1~}, y{~2~} ≤ [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
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")==
