comitat

Time limit: 0.03s Memory limit: 64MB Input: comitat.in Output: comitat.out

Toate seminţiile convieţuitoare pe Terra au hotărât ca hobbiţii, păstrătorii Inelului Puterii, să fie izolaţi într-o zonă a pământului numită Comitat. Hotarele Comitatului trebuie să fie reprezentate de un poligon convex cu câte un turn de pază în fiecare vârf.

Se cunosc poziţiile tuturor turnurilor din regiune (două numere naturale raportate la un sistem de axe rectangulare). Un paznic pe cal alb veghează hotarele comitatului parcugând, pe rând, toate distanţele dintre două turnuri succesive mergând pe drum minim, numai pe cărări paralele cu axele sistemului de axe.

Se cunoaşte lungimea maximă a drumului pe care-l poate parcurge paznicul la un tur complet al hotarelor comitatului şi se cere să se determine un poligon cu un număr maxim de turnuri pe contur, poligon ce poate constitui hotarul comitatului. În plus, hotarul trebuie să conţină turnul din Mordor (de coordonate 0 şi 0) într-un vârf, în fiecare dintre celelalte vârfuri aflându-se obligatoriu unul din turnurile existente.



De exemplu, pentru amplasamentul turnurilor ilustrat alăturat şi pentru limita de 25 Km a unui tur efectuat de paznic, hotarul comitatului poate fi format, în această ordine, din turnurile de coordonate (0,0), (4,1), (8,3), (4,4), (1,4), (0,0). Se observă că poligonul determinat de aceste turnuri este un poligon convex cu 5 turnuri pe contur.
Poligonul cu vârfurile (0,0), (4,1), (4,12), (0,7), (0,0) are tot 5 turnuri pe contur, dar un tur complet al acestui poligon depăşeşte 25 Km.

Date de intrare

Din fişierul comitat.in se citește de pe primul rând n, numărul de turnuri din ţinut (cu excepţia turnului implicit – Mordor), pe următoarele n rânduri xi  yix_i\; y_i, coordonatele (abscisă ordonată) ale fiecăruia dintre cele n turnuri, iar pe ultimul rând L, numărul reprezentând lungimea maximă a unui tur complet al poligonului.

Date de ieşire

În fişierul comitat.out se scrie pe primul rând v (numărul de turnuri de pe conturul poligonului) iar pe al doilea t1  t2  ...  tv1t_1\; t_2 \; ...\; t_{v-1}, numerele de ordine (în ordinea din fişierul de intrare) ale turnurilor de pe contur, pornind de la turnul Mordor (care este implicit) şi respectând succesiunea în sens trigonometric sau în sensul acelor de ceasornic a turnurilor de pe contur.

Observaţii

  • Pot exista turnuri strict în interiorul poligonului, dar acestea nu sunt luate în considerare pentru criteriul de maxim.
  • Se consideră soluţii şi poligonul degenerat format dintr-un singur vârf (Mordor) sau din două vârfuri (Mordor şi un alt turn) sau din mai multe vârfuri coliniare.
  • Pot exista turnuri coliniare pe conturul poligonului determinat.
  • Dacă există mai multe soluţii ce respectă condiţiile din enunţ, se va furniza doar una dintre acestea.
  • În fişierul de intrare nu există două turnuri ale căror poziţii să coincidă şi nu există un turn în poziţia (0,0).

Restricţii

  • 0 < n ≤ 50
  • 0xi,yi2000 ≤ x_i,y_i ≤ 200
  • 0 < L < 1000

Exemplu

comitat.in

9 
0 7
1 4
2 2
4 1
4 4
4 9
8 3
9 9
10 5
25

comitat.out

5
4 7 5 2

Log in or sign up to be able to send submissions!