| Fişierul intrare/ieşire: | antitir.in, antitir.out | Sursă | Baraj Shumen 2012, Juniori |
| Autor | Cristian Francu | Adăugată de |  Cristian Francu •francu |
| Timp execuţie pe test | 0.8 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.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.in | antitir.out | Explicaţ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. |
