Fişierul intrare/ieşire:	afaceri2.in, afaceri2.out	Sursă	Lot Resița 2012 - Baraj 3 Seniori
Autor	Zoltan Szabo	Adăugată de	Simoiu Robert •SpiderMan
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Afaceri2

Omul de afaceri Bill este foarte prosper şi are o reţea de magazine în n ţări. Cele n ţări sunt numerotate de la 1 la n şi reprezentându-le într-un sistem cartezian, fiecare ţară i se învecinează cu ţările i-1 şi i+1 (cu excepţia ţărilor 1 şi n, care au doar câte un singur vecin). Fiecare ţară i are suprafaţă dreptunghiulară şi are exact 4 aeroporturi ale căror coordonate sunt numere întregi.
Bill locuieşte în ţara 1 şi doreşte să se întâlnească cu câte un director economic din fiecare ţară pentru discuţii foarte importante. Cum timpul nu îi permite staţionarea, el va convoca directorii direct la aeroportul unde va ateriza avionul.
Se ştie că domiciliul stabil al lui Bill este în ţara 1 (ţara cel mai din stânga). El se va deplasa cu avionul parcurgând ţările de la stânga spre dreapta până ce va ajunge în ţara n, apoi de la dreapta la stânga până ce va ajunge înapoi în ţara 1 în aeroportul de unde a pornit, şi în fiecare ţară se va opri câte o singură dată, fie la dus, fie la întoarcere. Pe parcursul călătoriei va alege convenabil aeroporturile astfel încât lungimea drumului parcurs să fie minimă.

Cerinţă

Să se calculeze lungimea drumului minim. Rezultatul se va tipări ca un număr real.

Date de intrare

Fişierul afaceri.in conţine pe prima linie numărul de ţări n. Următoarele 4*n linii conţin câte două numere naturale x şi y separate prin spaţiu, reprezentând câte o coordonată a unui aeroport. Primele 4 linii conţin coordonatele aeroporturilor din prima ţară, următoarele 4 linii conţin aeroporturile din a doua ţară, etc.

Date de ieşire

Fişierul afaceri.out va conţine un singur număr real, lungimea drumului minim parcurs de Bill.

Restricţii

• 1 ≤ n ≤ 300
• 0 ≤ x_i ≤ 45 000
• 0 ≤ y_i ≤ 3 000
• Graniţele ţărilor sunt linii orizontale şi verticale, poziţia lor neavând nicio semnificaţie în problema noastră. Aeroporturile sunt strict în interiorul ţărilor, şi nu sunt ordonate după x sau y.
• Corectitudinea soluţiei se va verifica cu o precizie de 0.001.

Exemplu

afaceri2.in	afaceri2.out	Explicaţie
4 1 1 1 3 1 10 1 6 2 3 2 1 2 9 2 10 3 4 3 6 3 5 3 7 4 4 4 3 4 2 4 1	6.472136	Avem 4 ţări. Aeroporturile au coordonatele: 1: (1, 1) (1, 3) (1, 6) (1, 10) 2: (2, 1) (2, 3) (2, 9) (2, 10) 3: (3, 4) (3, 5) (3, 6) (3, 7) 4: (4, 1) (4, 2) (4, 3) (4, 4)   Lungimea drumului parcurs este de 6.472136 şi este desenat în exemplul de mai sus.

Cum se trimit solutii?