Segmente

seg

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

Se dau $N$ segmente. Sa se afle lungime minima a unei linii frante inchise care contine segmentele date pe laturile ei. Linia franta trebuie sa se poata desena pornind de la un punct oarecare de pe ea, mergand pe fiecare latura o singura data si ajungand inapoi la punctul de pornire (linia se poate autointersecta).

 se dau N segmente. Ele cun unite daca exista un poligon care le contine pe toate ca laturi. care este perimetrul nimim pe care il are un poligon care uneste cele N segmente.

h2. Date de intrare

Prima linie va contine numarul $T$ de teste, urmeaza $T$ teste. Pe prima linie a unui test se va afla numarul $N$, pe urmatoarele $N$ lini se vor vor afla coordonatele capetelor segmentelor.

N segmente ....

h2. Date de iesire

Pentru fiecare test se va afisa lungimea linilor care trebuie desenate, afisata cu $6$ zecimale cu aproximare.

...raspunsu

h2. Restrictii

* $1$ ≤ $N$ ≤ $17$
* Coordonatele punctelor se afla in intervalul $[ -2000 , 2000 ]$
* In fisierul de intrare se vor afla maxim $500$ teste dintre care cel mult $4$ vor avea $N > 10$
* Pentru fiecare test raspunsul va fi considerat corect numai daca diferenta in valoare absoluta intre raspunsul oficial si cel al concurentului este mai mica sau egala cu 10^-6^.

* ceva legat de N

h2. Exemplu

table(example). |_. seg.in |_. seg.out |

|2
 2
 1 1 1 2
 1 1 2 2
 3
 -931.693980 781.297764 -767.512077 1305.542158
 933.100984 -166.303237 1225.734021 -125.170151
 320.771418 -163.911119 -148.087080 -332.428961
| 1.000000
  4427.669962

| 0
| +inf

|

h3. Explicatie

la testul $1$ se uneste $1 2$ cu $2 2$ si se obtine lungimea $1$

...

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

3430