== include(page="template/taskheader" task_id="drept3") ==
Poveste şi cerinţă...
Se consideră $n$ cartoane albastre de formă pătrată. Aceste cartoane se aşează pe o foaie albă de hârtie, având formă dreptunghiulară, suficient de mare, astfel încât cartoanele să încapă în întregime pe foaie. Laturile cartoanelor sunt paralele cu laturile foii. Coordonatele vârfurilor cartoanelor sunt numere naturale. Cartoanele pot fi suprapuse integral sau parţial. Considerăm că foaia alba are colţul stânga-jos de coordonate $(0,0)$.
h2. Cerinţă
Să se determine:
a) aria totală a suprafeţei albastre care se va vedea, privind foaia de hârtie de sus;
b) numărul maxim de cartoane care au cel puţin o suprapunere comună.
h2. Date de intrare
Fişierul de intrare $drept3.in$ ...
Pe prima linie a fişierului de intrare $drept3.in$ se află un număr natural $n$, reprezentând numărul cartoanelor. Pe fiecare dintre următoarele $n$ linii sunt câte trei numere naturale $x$, $y$ şi $d$, despărţite prin câte un spaţiu, numere care descriu cartoanele. Cele trei numere $x$, $y$ şi $d$ corespund unui carton pătrat $ABCD$ având următoarele coordonate: $A(x,y)$, $B(x+d,y)$, $C(x+d,y+d)$, $D(x,y+d)$.
h2. Date de ieşire
În fişierul de ieşire $drept3.out$ ...
Pe prima linie a fişierului de ieşire $drept3.out$ se va scrie o valoare un număr natural reprezentând aria totală ocupată de cartoanele albastre pe foaia albă, iar pe a doua linie un număr natural ce reprezintă numărul maxim de cartoane care au cel puţin o suprapunere comună.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 10000$
* $0 ≤ x, y, d ≤ 5000$
* Aria oricărei suprafeţe albastre este strict mai mică decât $2^31^$
* Pentru determinarea corectă a valorii de la de la cerinţa a) se acordă 40% din punctajul acordat testului respectiv, iar pentru determinarea corectă a valorii de la cerinţa b) se acordă 60% din punctajul acordat testului respectiv.
h2. Exemplu
table(example). |_. drept3.in |_. drept3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
table(example). |_. drept3.in |_. drept3.out |_. Explicaţie |
| 4
1 1 2
2 0 2
3 1 2
5 3 1
| 11
2
| !problema/drept3?exemplu1.jpg 90x90!
|
table(example). |_. drept3.in |_. drept3.out |_. Explicaţie |
| 4
1 1 4
2 2 3
3 3 2
4 4 1
| 16
4
| !problema/drept3?exemplu2.jpg 90x90!
|
...
== include(page="template/taskfooter" task_id="drept3") ==
== include(page="template/taskfooter" task_id="drept3") ==
