Fișierul intrare/ieșire antitir.in, antitir.out Sursă Baraj Shumen 2012, Juniori
Autor Cristian Frâncu Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.8 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii