photoshop

Photoshop

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

Au trecut deja 2 saptamani de cand TU lurezi la Adobe in echipa Photoshop. Timpul de acomodare e aproape pe sfarsite si e timpul sa lucrezi la prima ta bucata de cod din productie. Pentru inceput trebuie sa lucrezi la o noua unealta de selectie care functioneaza in modul urmator: utilizatorul indica un dreptunghi de selectie peste continut iar dreptunghiul este automat micsorat astfel incat aria lui este minima si tot continutul indicat de utilizator este acoperit.

Au trecut deja doua saptamani de cand tu esti angajat la Adobe in echipa Photoshop. Timpul de acomodare e aproape pe sfarsite si a venit momentul sa lucrezi la prima ta bucata de cod din productie. Pentru inceput trebuie sa lucrezi la o noua unealta de selectie a continutului care functioneaza in modul urmator: utilizatorul indica un dreptunghi de selectie peste continut de pe panza de lucru iar dreptunghiul este automat micsorat astfel incat aria lui este minima si tot continutul indicat de utilizator este acoperit.

Pentru a intelege mai bine cum trebuie sa functionele unealta ai primit urmatoarea diagrama:

Pentru a intelege mai bine cum trebuie sa functioneze unealta ai primit urmatoarea diagrama:

TODO : Adauga poza

!problema/photoshop?Photoshop.png!

Legenda:

* albastru: continutul

* albastru: continutul de pe panza de lucru

* rosu: dreptunghiul de selectie indicat de utilizator

* verde: dreptunghiul micsorat
 
Dat fiind continutul la un moment dat si un dreptunghi de selectie, calculeaza dreptunghiul de arie minima care acopera acelasi ontinut ca dreptunghiul dat.

* verde: dreptunghiul dupa ce a fost micsorat automat
Pentru testarea uneltei utilizatorul dispune doar de urmatoarele actiuni:
# Adaugarea unui punct pe panza de lucru
# Stergerea unui punct de pe panza de lucru
# Indicarea unui dreptunghi de selectie
Date fiind toate actiunile utilizatorului, pentru fiecare actiune de selectie calculeaza dreptunghiul de arie minima care acopera acelasi continut ca dreptunghiul dat.
h2. Date de intrare
Fisierul de intrare $photoshop.in$ contine pe prima linie un numar $N$ reprezentand numarul de interactiuni ale utilizatorului cu Photoshop-ul. Pe urmatoarele $N$ linii sunt descrise actiunile utilizatorului in felul urmator:

h2. Date de intrare

* $0 X Y$ : adauga punctul $(X, Y)$ pe panza de lucru
* $1 X Y$ : sterge punctul $(X, Y)$ de pe panza de lucru
* $2 A B C D$ : activeaza noua unealta de selectie pe dreptunghiul care are coltul din stanga sus si cel din dreapta jos in punctul $(A, B)$ respectiv $(C, D)$.

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

h2. Date de iesire

h2. Date de ieşire

Fisierul de iesire $photoshop.out$ va contine cate o linie pentru fiecare actiune de tip $2$ ( activarea uneltei de selectie ) in ordinea in care apar in fisierul de intrare. Fiecare linie va descrie dreptunghiul micsorat prin coltul din stanga sus si coltul din dreapta jos in acelasi mod in care sunt specificate in fisierul de intrare.
Daca dreptunghiul de selectie nu contine nici un punct, atunci se va afisa "-1" ( fara ghilimele ).

În fişierul de ieşire $photoshop.out$ ...
h2. Restricţii

h2. Restrictii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 100000$
* $0 ≤ X, Y, A, B, C, D ≤ 100000$
* Coordonatele sunt numere naturale

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

| 9
  0 2 2
  0 4 4
  0 5 3
  2 1 5 6 1
  0 6 6
  2 1 5 6 1
  0 3 3
  1 2 2
  2 1 7 6 1
| 2 4 5 2
  2 4 5 2
  3 6 6 3
|

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

8867