Poligon7

poligon7

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

!>{width:50%}problema/poligon7?pic_poligon7.png!
 
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.

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:
 
# Costul minim $ans$ al unei succesiuni de mutări care reduce poligonul la un singur punct;
# O succesiune de mutări de cost minim.

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.

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

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:
 
# 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ț.
# 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ă.

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 ≤ 2 000$
* 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ă.

• 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ă.

h2. Exemplu

2 1
|

h3. Explicaţie
 
...
 

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