== include(page="template/taskheader" task_id="afaceri2") ==

Poveste şi cerinţă...

p<>. 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ă.
 
h2. Cerinţă
 
Să se calculeze lungimea drumului minim. Rezultatul se va tipări ca un număr real.

h2. Date de intrare

Fişierul de intrare $afaceri2.in$ ...

p<>. 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.

h2. Date de ieşire

În fişierul de ieşire $afaceri2.out$ ...

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

h2. 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$.

h2. Exemplu

table(example). |_. afaceri2.in |_. afaceri2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. 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)
{!<>problema/afaceri2?x.png!}
Lungimea drumului parcurs este de $6.472136$ şi este desenat în exemplul de mai sus.
|

== include(page="template/taskfooter" task_id="afaceri2") ==

8504