Fişierul intrare/ieşire:antitir.in, antitir.outSursăBaraj Shumen 2012, Juniori
AutorCristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.8 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Antitir

Notă: este necesară o implementare eficientă.

Se dau coordonatele a n săgeţi înfipte într-un panou. Coordonatele săgeţilor sînt întregi. Pot exista mai multe săgeţi în aceelaşi punct din panou. Dispunem de o ţintă care poate fi deplasată pe panou astfel încît centrul ei să fie aliniat la coordonate întregi. Pentru o săgeată aflată la distanţă x pe orizontală şi y pe verticală de centrul ţintei ea acordă x + y puncte.

Cerinţă

Să se găsească o poziţionare a ţintei pe panou astfel încît suma punctajului săgeţilor să fie minimă.

Date de intrare

Prima linie a fişierului antitir.in conţine numărul de săgeţi, n. Următoarele n linii conţin cîte o pereche de numere (x i, y i), coordonatele unei săgeţi.

Date de ieşire

Fişierul antitir.out va conţine un singur număr, punctajul minim care se poate obţine.

Restricţii

  • 1 ≤ n ≤ 1000000
  • -1000000000 ≤ x i, y i ≤ 1000000000 (x i şi y i fiind coordonatele săgeţilor)
  • În 60% din teste 0 ≤ x i, y i ≤ 1000000
  • În 30% din teste n ≤ 1000 şi 0 ≤ x i, y i ≤ 1000

Exemple

antitir.inantitir.outExplicaţie
4
1 -1
1 1
-1 1
-1 -1
8
Oriunde am deplasa ţinta în interiorul pătratului definit de cele patru puncte,
sau pe perimetrul lui obţinem suma punctelor săgeţilor egală cu 8.
8
3 3
0 2
2 5
6 6
5 2
3 0
5 3
2 1
24
Dacă deplasăm ţinta cu centrul în punctul de coordonate (3, 2) obţinem suma
punctelor săgeţilor egală cu 24.
Trebuie sa te autentifici pentru a trimite solutii. Click aici