==Include(page="template/taskheader" task_id="tribute")==
 
==Include(page="template/raw")==
 
Link: [1]File-List
 
Tribute to M (you will always be in our souls)
 
 
 
Din nou cineva trebuie sa cumpere teren... De data asta este Viviana si terenul pe care vrea sa-l cumpere e in forma de dreptunghi cu laturile pararele cu axele sistemului de coordonate. Se cunoaste pozitia a N obiective situate in puncte de coordanate intregi pe care Viviana vrea sa le aibe cat mai aproape de terenul sau. Dupa ce si-a stabilit pozitia terenului ea incepe sa calculeze distanta totala de la terenul ei la cele N obiective. Pentru aceasta ea defineste distanta de la un obiectiv la terenul sau ca fiind distanta Manhattan minima de la obiectiv la orice punct de coordonate intregi care se afla pe propietatea ei sau pe marginile acesteia (bineinteles, conform acestei definitii, obiectivele aflate pe propietatea Vivianei sau pe marginile acesteia se vor afla la distanta 0 fata de terenul sau). Distanta totala de la propietatea la obiective este suma distantelor pentru fiecare obiectiv in parte.
 
h2. Cerinta
 
Aflati pentru Viviana distanta totala minima pe care o poate obtine daca ea vrea sa cumpere un teren de dimensiuni (DX,DY). Merita, ca e fata frumoasa ;).
 
h2. Date de Intrare
 
Fisierul de intrare tribute.in contine pe prima linie numerele N, DX si DY , separate prin spatii. Pe urmatoarele N linii se afla pozitia fiecarui obiectiv in plan.
 
h2. Date de Iesire
 
Fisierul de iesire tribute.out trebuie sa contina un singur numar reprezentand distanta totala minima pe care o poate obtine Viviana prin plasarea inteligenta a terenului.
 
h2. Restrictii si precizari
 
S 1 <= N <= 50.000
 
S 1 <= DX, DY <= 50.000
 
S Coordonatele obiectivelor sunt numere naturale din intervalul [0, 50.000]
 
S Nu exista mai multe obiective in acelasi punct.
 
S Coordonatele terenului nu pot fi inversate.
 
S Terenul se poate plasa oriunde in plan.
 
S Distanta Manhattan intre doua puncte (x, y) si (z, t) se defineste ca fiind |x-z| + |y-t|
 
S "Viviana" este dedicatie speciala pentru Mort care a vrut fete in probleme. Traisca fetele (si Viviana printre ele)!!!
 
S Obiectivele sunt de fapt baieti pe care Viv vrea sa ii aibe cat mai aproape de inima ei.
 
S M nu a murit (Domne fereste!) ci din contra: e alive`n kickin` !!!.
 
h2. Exemplu
 
tribute.in tribute.out
5 1 1 10
 
4 4
 
0 0
 
4 1
 
0 1
 
4 3
 
 
 
Explicatii
 
Coltul din stanga jos al terenului se plaseaza in punctul (3, 1). Distantele de la teren la obiective sunt:
 
2, 4, 0, 3 si respectiv 1. Distanta totala : 2+4+0+3+1 = 10 care este cea minima (sper).
 

==Include(page="template/taskheader" task_id="tribute")==
 
Din nou cineva trebuie sa cumpere teren... De data asta este Viviana si terenul pe care vrea sa-l cumpere e in forma de dreptunghi cu laturile pararele cu axele sistemului de coordonate. Se cunoaste pozitia a $N$ obiective situate in puncte de coordanate intregi pe care Viviana vrea sa le aibe cat mai aproape de terenul sau. Dupa ce si-a stabilit pozitia terenului ea incepe sa calculeze distanta totala de la terenul ei la cele $N$ obiective. Pentru aceasta ea defineste distanta de la un obiectiv la terenul sau ca fiind distanta Manhattan minima de la obiectiv la orice punct de coordonate intregi care se afla pe propietatea ei sau pe marginile acesteia (bineinteles, conform acestei definitii, obiectivele aflate pe propietatea Vivianei sau pe marginile acesteia se vor afla la distanta 0 fata de terenul sau). Distanta totala de la propietatea la obiective este suma distantelor pentru fiecare obiectiv in parte.
 
h2. Cerinta
 
Aflati pentru Viviana distanta totala minima pe care o poate obtine daca ea vrea sa cumpere un teren de dimensiuni ({$DX$},{$DY$}).
 
h2. Date de intrare
 
Fisierul de intrare $tribute.in$ contine pe prima linie numerele $N$, $DX$ si $DY$, separate prin spatii. Pe urmatoarele $N$ linii se afla pozitia fiecarui obiectiv in plan.
 
h2. Date de iesire
 
Fisierul de iesire $tribute.out$ trebuie sa contina un singur numar reprezentand distanta totala minima pe care o poate obtine Viviana prin plasarea inteligenta a terenului.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 50.000$
* $1 ≤ DX, DY ≤ 50.000$
* Coordonatele obiectivelor sunt numere naturale din intervalul $[0, 50 000]$
* Nu exista mai multe obiective in acelasi punct
* Coordonatele terenului nu pot fi inversate
* Terenul se poate plasa oriunde in plan
* Distanta Manhattan intre doua puncte ({$x$}, {$y$}) si ({$z$}, {$t$}) se defineste ca fiind $|x-z| + |y-t|$
 
h2. Exemplu
 
table(example). |_. tribute.in |_. tribute.out |
|5 1 1
4 4
0 0
4 1
0 1
4 3
|10 |
 
h3. Explicatie
 
Coltul din stanga jos al terenului se plaseaza in punctul (3, 1). Distantele de la teren la obiective sunt: 2, 4, 0, 3 si respectiv 1. Distanta totala este 2+4+0+3+1 = 10, care este cea minima.
 
 
==Include(page="template/taskfooter" task_id="tribute")==

References
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/tribute/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="tribute")==

99