Fişierul intrare/ieşire:poligon5.in, poligon5.outSursăGrigore Moisil 2011, Clasele 11-12
AutorAndrei Paul Puni, Perticas CatalinAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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. fiecare latură a poligonului dat sa conţină exact un vârf al poligonului nou
  5. 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 xi şi yi 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 Pi, reprezentând perimetrul minim al poligonului cerut de testul i.

Restricţii

  • 3 ≤ N ≤ 200
  • 1 ≤ T ≤ 10
  • -10 000 ≤ xi, yi ≤ 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 (xi, yi) şi (xj, yj), distanţa este (xi-xj)2 + (yi-yj)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.

Exemplu

poligon5.inpoligon5.out
1
7
9 0
2 7
0 13
3 16
11 16
16 11
14 5
268

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content