Fișierul intrare/ieșire | antitir.in, antitir.out | Sursă | Baraj Shumen 2012, Juniori |
---|---|---|---|
Autor | Cristian Frâncu | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.8 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile 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. |