Fişierul intrare/ieşire:tribute.in, tribute.outSursăpreONI 2004
AutorMihai Stroe, Silviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

Cerinta

Aflati pentru Viviana distanta totala minima pe care o poate obtine daca ea vrea sa cumpere un teren de dimensiuni (DX,DY).

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.

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.

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|

Exemplu

tribute.intribute.out
5 1 1
4 4
0 0
4 1
0 1
4 3
10

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content