== include(page="template/taskheader" task_id="poligon5") ==
Poveste şi cerinţă...
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:
# să fie un poligon convex cu vârfurile având coordonate întregi
# să aibă acelaşi număr de vârfuri ca poligonul iniţial
# să fie înscris în poligonul iniţial, dar să nu aibă vârfuri comune cu acesta
# fiecare latură a poligonului dat sa conţină exact un vârf al poligonului nou
# să aibă perimetrul minim posibil
h2. 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.
h2. Date de intrare
Fişierul de intrare $poligon5.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $poligon5.out$ ...
Î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$.
h2. 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~})^2^ + (y{~i~}-y{~j~})^2^$.
* 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$.
h2. Exemplu
table(example). |_. poligon5.in |_. poligon5.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
7
9 0
2 7
0 13
3 16
11 16
16 11
14 5
| 268
|
h3. 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)$.
== include(page="template/taskfooter" task_id="poligon5") ==
