Fișierul intrare/ieșire	examen.in, examen.out	Sursă	Olimpiada locală 2015, clasele 11-12
Autor	Rodica Pintea	Adăugată de	Ana Rogoz • anarogoz
Timp de execuție pe test	0.1 sec	Limită de memorie	5000 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Examen (clasele 11-12)

La școala militară galactică, o mulțime de N dispozitive amorsate fictiv sunt plasate pe un teren plan, în puncte de coordonate întregi. Dispozitivele sunt numerotate de la 1 la N. Elevul WXP7 aflat la școala militară, pentru a trece o probă de examen, se va plasa într-un punct al terenului (tot de coordonate întregi) și va dezamorsa dispozitivele, în ce ordine dorește, folosind o telecomandă cu raza laser de acțiune reglabilă.
Astfel, el va regla telecomanda EXACT pentru distanța Manhattan la care se află un dispozitiv și va acționa cu ea asupra dispozitivului dezamorsându-l, apoi va regla telecomanda EXACT pentru distanța Manhattan la care se află un alt dispozitiv și va acționa cu ea dezamorsandu-l etc. până ce toate dispozitivele vor fi dezamorsate.
Costul total de dezamorsare (cel care va stabili calificativul elevului WXP7) este dat de distanța reglată pentru primul dispozitiv plus diferența (în valoare absolută) dintre distanța reglată inițial și distanța reglată pentru al doilea dispozitiv, plus diferența (în valoare absolută) dintre distanța reglată pentru al doilea dispozitiv și distanța reglată pentru al treilea dispozitiv etc. De exemplu, dacă sunt 4 dispozitive și ele, în ordinea în care sunt dezamorsate, se află la distanțele 8, 6, 2 și respectiv 8 de punctul în care se află WXP7 cu telecomanda, atunci costul inițial este 8, la care se adaugă 2 (8-6), la care se adaugă 4 (6-2), la care se mai adaugă 6 (8-2), obținând costul total 20.
Dacă poziția în care s-a plasat WXP7 conține unul dintre dispozitive, el se va dezamorsa automat, cu costul 0.
Cunoscându-se numărul N de dispozitive și pozițiile acestora în plan, să se determine costul total minim de dezamorsare și numărul de poziții în care se poate plasa WXP7, astfel încât, în oricare dintre aceste poziții s-ar situa WXP7, va exista o strategie prin care poate obține acest cost minim de dezamorsare.

Date de intrare

Din fișierul examen.in se citesc: – de pe prima linie un număr natural N reprezentând numărul de dispozitive – de pe următoarele N linii, câte două numere întregi, Xi Yi (i{1,…,N}), despărțite prin câte un spațiu, reprezentând coordonatele întregi, întâi abscisa și apoi ordonata, ale fiecărui dispozitiv.

Date de ieșire

În fișerul examen.out se afișează: – pe prima linie un număr natural C, reprezentând costul minim de dezamorsare – pe linia următoarele un număr natural P reprezentând numărul de poziții în care se poate plasa WXP7 pentru a realiza un cost minim de dezamorsare

Restricții

• 0 < N < 100000 • –10000 ≤ Xi ≤ 10000 ; –10000 ≤ Yi ≤ 10000 • Distanța Manhattan între două puncte cu coordonatele X1, Y1 și respectiv coordonatele X2, Y2 se calculează cu ajutorul formulei: |X1-X2|+|Y1-Y2| • Pentru fiecare dintre cele două valoari, C și P, se acordă 50% din punctaj • Pentru 50% din teste, toate numerele din problemă sunt numere cu cel mult 4 cifre h2. Exemplu

examen.in	examen.out
4 1 1 6 1 6 6 3 4	5 2

examen.in	examen.out
4 1 1 6 1 6 6 1 6	6 4

Explicație

Exemplul 1. Pentru dispozitivele numerotate de la 1 la 4 din figura alăturată, elevul se poate situa în oricare dintre cele două poziții de coordonate 4 3 și respectiv 5 2 pentru a obține costul minim de dezamorsare, 5. Pentru amplasarea în punctul de coordonate 4 3, acest cost se obține dezamorsând întâi dispozitivul 4 (reglaj1=dist1=2), apoi dispozitivul 2 (reglaj2= |dist1-dist2|=2), apoi dsipozitivul 3 (reglaj3= |dist2-dist3|=1 și în final dispozitivul 1 (reglaj 4=|dist3-dist4|=0).

Exemplul 2