După ce elfii au reușit să înlăture amenințarea orcilor, ei au decis să se izoleze pentru o vreme.
Hotarele Pădurii Aurii în care locuiesc elfii, vor fi 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 elf veghează hotarele Pădurii Aurii parcugând, pe rând, toate distanțele dintre două turnuri succesive mergând pe cel mai scurt drum, numai pe cărări paralele cu axele. Se cunoaște lungimea maximă a drumului pe care-l poate parcurge paznicul la un tur complet al hotarelor Pădurii Aurii și trebuie să se determine un poligon cu un număr maxim de turnuri pe contur, poligon care poate constitui hotarul Pădurii Aurii. În plus, hotarul trebuie să conțină turnul din Poiana Argintie (de coordonate 0 și 0) într-un vârf, iar în fiecare dintre celelalte vârfuri se află, obligatoriu, unul dintre turnurile existente.
Fișierul de intrare INPUT.TXT conține pe prima linie numărul n al turnurilor din regiune (turnul din Poiana Argintie nu este numărat).
Pe fiecare dintre următoarele n linii se află câte două numere naturale, despărțite printr-un spațiu, care reprezintă coordonatele unuia dintre turnuri. Ultima linie a fișierului conține lungimea maximă l a unui tur complet al poligonului.
Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie numărul k al turnurilor de pe conturul poligonului (incluzând turnul din Poiana Argintie).
Pe fiecare dintre următoarele k - 1 linii se va afla câte un număr întreg, reprezentând numărul de ordine al unui turn de pe contur, pornind de la turnul din Poiana Argintie (care nu este afișat) și respectând succesiunea în sens trigonometric sau antitrigonometric a turnurilor de pe contur.
INPUT.TXT
9 0 7 1 4 2 2 4 1 4 4 4 9 8 3 9 9 10 5 25 OUTPUT.TXT 5 4 7 5 2
|