Fişierul intrare/ieşire:	poligon5.in, poligon5.out	Sursă	Grigore Moisil 2011, Clasele 11-12
Autor	Andrei Paul Puni, Perticas Catalin	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Poligon5

Mitruţ, motanul încălţat are o grădină fermecată în formă de poligon convex cu vârfurile având coordonate întregi, dar din cauza că doarme prea mult, nu are timp s-o îngrijească în întregime. De aceea, el vrea să renunţe la unele părţi din grădină, dar vrea ca noua grădină să respecte totuşi unele condiţii:

1. să fie un poligon convex cu vârfurile având coordonate întregi
2. să aibă acelaşi număr de vârfuri ca poligonul iniţial
3. să fie înscris în poligonul iniţial, dar să nu aibă vârfuri comune cu acesta
4. să aibă perimetrul minim posibil

Cerinţă

Determinaţi perimetrul minim pentru noua grădină fermecată a lui Mitruţ. Mitruţ vă pune la dispoziţie T astfel de teste pentru a fi sigur că nu îl păcăliţi de 1 Aprilie. 

Date de intrare

Pe prima linie a fişierului de intrare poligon5.in se află numărul T de teste din fişier. Prima linie a fiecărui test conţine numărul N de vârfuri ale poligonului iniţial. Pe următoarele N linii se află câte două numere întregi x_i şi y_i reprezentând coordonatele vârfurilor unui poligon. Vârfurile sunt date în sensul acelor de ceasornic.

Date de ieşire

În fişierul de ieşire poligon5.out se află T numere întregi. Pe linia i se află numărul P_i, reprezentând perimetrul minim al poligonului cerut de testul i.

Restricţii

• 3 ≤ N ≤ 200
• 1 ≤ T ≤ 10
• -10 000 ≤ x_i, y_i ≤ 10 000
• Numărul de puncte având coordonate întregi de pe conturul poligonului nu va depăşi 200.
• Pentru simplitate vom considera că distanţa dintre oricare două puncte este pătratul distanţei euclidiene. Deci, pentru două puncte de coordonate (x_i, y_i) şi (x_j, y_j), distanţa este (x_i-x_j)² + (y_i-y_j)².
• Se garantează că fiecare latură a poligonului iniţial are cel puţin un punct de coordonate întregi.
• Pentru 10% din teste, fiecare latură a poligonului iniţial va avea exact un punct de coordonate întregi.
• Pentru alte 20% din teste, numărul de puncte de coordonate întregi de pe oricare latură nu depăşeşte 3, iar N ≤ 12 şi T ≤ 5.

Exemplu

Explicaţie

În total avem 25 de puncte de coordonate întregi pe conturul poligonului. Din acestea, vârfurile alese pentru noul poligon sunt: (5,4), (1,10), (2,15), (7,16), (13,14), (15,8), (13,4).

Cum se trimit solutii?