demolish

Demolish

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

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

Poveste ...

Patratel a strans profit serios din afacerile cu struti si acum doreste sa se extinda. Cu banii pe care ii are intentioneaza sa isi construiasca o ferma in regiune. Regiunea este de forma dreptunghiulara si are $M$ kilometri lungime si $N$ kilometri latime, iar ferma trebuie sa fie si ea dreptunghiulara si sa aiba laturile paralele cu ale regiunii. In regiune sunt insa construite alte $F$ ferme ale unor oameni la fel de bogati ca si Patratel, ferme tot dreptunghiulare si tot cu laturile paralele cu ale regiunii. Patratel este om pretentios ( ca si strutii sai, de altfel ), si doreste o ferma de $DX$ kilometri lungime si $DY$ kilometri latime. Constructia unei astfel de ferme nu este intotdeauna posibila pentru ca depinde de asezarea celorlalte $F$ ferme. Fiecare ferma are un cost de demolare ( costul pe care Patratel trebuie sa il plateasca sa demoleze ferma respectiva ). El doreste sa isi plaseze ferma proprie in regiune astfel incat suma costurilor de demolare ale fermelor intersectate de ferma sa fie minima.
Doua ferme se intersecteaza daca si numai daca un punct de pe laturile primei ferme se gaseste strict in interiorul celei de a doua ferme ( adica ele nu se intersecteaza daca se ating doar laturile ).

h2. Cerinta

...

Sa se determina costul minim pe care il plateste Patratel pentru a-si construi ferma.

h2. Restrictii

h2. Date de Intrare

...

Prima linie a fisierului $demolish.in$ contine cinci numere naturale $M, N, F, DX$ si $DY$ ( in aceasta ordine ), cu semnificatia din enunt. Fiecare din urmatoarele $F$ linii contine tot cate cinci numere, $(x1 y1 x2 y2 C)$, unde $(x1 y1)$ reprezinta coordonatele coltului stanga-jos ale unei ferme din regiune, $(x2 y2)$ coordonatele dreapta-sus ale aceleiasi ferme, iar C costul de demolare al fermei respective. Pentru un astfel de set avem intotdeauna $0 &le; x1 < x2 &le; M, 0 &le; y1 < y2 &le; N$ si $0 &le; C &le; 200 000$.

h2. Date de intrare

h2. Date de Iesire

...

Prima linie a fisierului demolish.out contine $COST$, costul minim cerut. A doua linie contine patru numere intregi separate de cate un spatiu, $(x1 y1 x2 y2)$, reprezentand pozitionarea fermei in regiune: $(x1 y1)$ - coordonatele coltului stanga-jos si $(x2 y2)$ - coordonatele dreapta-sus a fermei construite de Patratel pentru a obtine costul minim $COST$. Daca sunt mai multe posibilitati de amplasare, se va afisa cea care are $x1$ minim, iar daca si in acest caz sunt mai multe posibilitati, se va afisa cea care are $y1$ minim.

h2. Date de iesire

h2. Restrictii si precizari

...

* $4 < M, N < 500 001$
* $0 < DX < M + 1, 0 < DY < N + 1$
* $F < 30 001$
* Evident, fermele deja construite in regiune nu se intersecteaza
* Oricare doua ferme nu se intersecteaza daca se ating doar laturile
* Pot exista doua ferme din cele $F$ care au acelasi cost de demolare

h2. Exemplu

| demolish.in | demolish.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. demolish.in |_. demolish.out |
| 12 10 6 7 8
2 3 5 8 3
5 7 7 9 7
8 4 12 8 22
7 1 9 2 4
0 0 1 2 10
1 9 2 10 6 |  14
1 0 8 8 |

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

h3. Explicatie
 
Costul minim se obtine daca ferma este dispusa conform coordonatelor (1 0 8 8), intersectand fermele 1, 2 si 4, care trebuiesc demolate. Suma costurilor tuturor demolarilor efectuate este de 3+7+4 = 14. O alta plasare posibila care duce tot la costul 14 este (1 1 8 9), dar aceasta nu duce la indeplinirea conditiei de minimalitate a coordonatelor.
 
==Include(page="template/taskfooter" task_id="demolish")==
 
 

807