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

Se consideră un poligon convex cu N laturi. Se vor
efectua N - 1 mutări. O mutare constă în alegerea a
două puncte A și B vecine pe poligon și mutarea
punctului A în B (vezi figura). Costul mutării este
egal cu distanța euclidiană dintre A și B. După
mutare punctul A este asimilat de B, iar procesul se
reia pe noul poligon. Se cere costul total minim al unei succesiuni de N - 1 mutări care reduce poligonul la un singur punct, precum și o modalitate de a obține acest cost.
 
h2. Cerinţe
 
Dându-se T poligoane convexe, să se determine:
1. Costul minim ans al unei succesiuni de mutări care reduce poligonul la un singur punct;
2. O succesiune de mutări de cost minim.

Poveste şi cerinţă...
 

h2. Date de intrare

Fișierul de intrare poligon.in conține pe prima linie un număr întreg p, reprezentând numărul cerinței ce
se cere a fi rezolvată.
Pe a doua linie a fișiereului de intrare se va afla T, reprezentând numărul de poligoane ce urmează să fie citite. Apoi, urmează cele T teste. Fiecare test are următoarea structură:
- pe prima linie numărul natural N, reprezentând numărul de laturi ale poligonului;
- pe următoarele N linii câte 2 numere întregi x și y, separate printr-un spațiu, reprezentând
coordonatele vârfurilor poligonului curent, Vârfurile sunt date în ordine trigonometrică.
h2. Date de ieşire
 
Fișierul de ieșire poligon.out va conține, în funcție de valoarea lui p, următoarele informații:
1. Dacă p = 1 se rezolvă doar cerința 1. Pentru fiecare dintre cele T teste se va afișa câte un număr real ans pe o linie, cu semnificația din enunț.
2. Dacă p = 2 se rezolvă doar cerința 2. Pentru fiecare din cele T teste se vor afișa câte N-1 linii, fiecare dintre aceste fiind de forma A B, reprezentând mutările în ordinea în care acestea se efectuează.
h2. Restricţii și precizări
 
• 1≤T≤5
• 1≤N≤2000
• Pentru toate vârfurile poligonului -1 000 000 ≤ x, y ≤ 1 000 000
• Nu vor exista 2 vârfuri ale poligonului aflate la aceleași coordonate.
• Poligonul nu este neapărat strict convex. Cu alte cuvinte, pot exista oricâte vârfuri consecutive
coliniare.
• Pentru teste în valoare de 5 puncte, N ≤ 7;
• Pentru alte teste în valoare de 10 puncte N ≤ 15;
• Pentru alte teste în valoare de 15 puncte N ≤ 50;
• Pentru alte teste in valoare de 15 puncte N ≤ 100;
• Pentru alte teste în valoare de 15 puncte N ≤ 500;
• Pentru alte teste în valoare de 40 puncte N ≤ 2000;
• Pentru rezolvarea cerinței 1. se acordă 80% din punctajul asociat testului.
• Pentru rezolvarea cerinței 2. se acordă 20% din punctajul asociat testului.
• Valoarea lui ans se va considera corectă dacă aceasta diferă față de răspunsul corect prin
maxim 10-6.
• ATENȚIE! După o mutare A B (în urma căreia vârful A a fost asimilat de vârful B), o mutare de
forma A C sau C A va fi considerată invalidă.

Fişierul de intrare $poligon7.in$ ...
 
h2. Date de ieşire
 
În fişierul de ieşire $poligon7.out$ ...
 
h2. Restricţii
 
* $... ≤ ... ≤ ...$

h2. Exemplu