Fişierul intrare/ieşire:	comitat.in, comitat.out	Sursă	ONI 2002, clasele 11-12
Autor	Rodica Pintea	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.075 sec	Limită de memorie	5096 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Comitat

Toate semintiile convietuitoare pe Terra au hotarat ca hobbitii, pastratorii Inelului Puterii, sa fie izolati intr-o zona a pamantului numita Comitat. Hotarele Comitatului trebuie sa fie reprezentate de un poligon convex cu cate un turn de paza in fiecare varf. Se cunosc pozitiile tuturor turnurilor din regiune (doua numere naturale raportate la un sistem de axe rectangulare). Un paznic pe cal alb vegheaza hotarele comitatului parcurgand, pe rand, toate distantele dintre doua turnuri succesive mergand pe drum minim, numai pe carari paralele cu axele sistemului de axe. Se cunoaste lungimea maxima a drumului pe care-l poate parcurge paznicul la un tur complet al hotarelor comitatului si se cere sa se determine un poligon cu un numar maxim de turnuri pe contur, poligon ce poate constitui hotarul comitatului. In plus, hotarul trebuie sa contina turnul din Mordor (de coordonate 0 si 0) intr-un varf, in fiecare dintre celelalte varfuri aflandu-se obligatoriu unul din turnurile existente. De exemplu, pentru amplasamentul turnurilor ilustrat mai jos si pentru limita de 25 Km a unui tur efectuat de paznic, hotarul comitatului poate fi format, in aceasta ordine, din turnurile de coordonate (0,0), (4,1), (8,3), (4,4), (1,4), (0,0). Se observa ca poligonul determinat de aceste turnuri este un poligon convex cu 5 turnuri pe contur. Poligonul cu varfurile (0,0), (4,1), (4,12), (0,7), (0,0) are tot 5 turnuri pe contur, dar un tur complet al acestui poligon depaseste 25 Km.

Date de intrare

Prima linie a fisierului de intrare comitat.in contine pe prima linie numarul intreg N, reprezentand numarul de turnuri din tinut. Pe urmatoarele N linii se afla cate 2 numere intregi, separate printr-un spatiu, reprezentand coordonatele x si y ale cate unui turn. Pe ultima linie a fisierului se afla numarul intreg L, reprezentand lungimea maxima a unui tur complet al poligonului.

Date de iesire

Pe prima linie a fisierului comitat.out se va afisa numarul maxim T de turnuri de pe conturul unui poligon avand proprietatile mentionate. Pe a doua linie veti afisa T - 1 numere intregi, separate prin cate un spatiu, reprezentand numerele de ordine ale turnurilor de pe conturul poligonului, in sens trigonometric sau in sens invers trigonometric. Turnul din Mordor nu se afisaza, el fiind considerat asezat intre primul si ultimul din cele T - 1 turnuri afisate.

Restrictii

• 1 ≤ N ≤ 50
• 0 ≤ coordonatele x si y ale oricarui punct ≤ 200
• 1 ≤ L ≤ 1000
• Pot exista turnuri strict in interiorul poligonului, dar acestea nu sunt luate in considerare pentru criteriul de maxim.
• Se considera solutii si poligonul degenerat format dintr-un singur varf (Mordor) sau din doua varfuri (Mordor si un alt turn) sau din mai multe varfuri coliniare.
• Pot exista turnuri coliniare pe conturul poligonului determinat.
• Daca exista mai multe solutii ce respecta conditiile din enunt, se va furniza doar una dintre acestea.
• In fisierul de intrare nu exista doua turnuri ale caror pozitii sa coincida si nu exista un turn in pozitia (0,0).

Exemplu

Cum se trimit solutii?