Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-11-07 16:31:57.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:melc.in, melc.outSursăRomanian Open Contest, TIMUS 2001
AutorMugurel Ionut AndreicaAdăugată deAndrei1998Andrei Constantinescu Andrei1998
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Melc

In Romania toti melcii sunt lenesi. Sa-l luam pe melcul Gigel, de exemplu. El are de vizitat N prieteni care sunt localizati la coordonate distincte in plan. Dar intrucat Gigel este prea lenes, el nu vrea sa iasa din casa. A zis, totusi, ca se va duce sa isi viziteze prietenii daca cineva ii poate arata drumul potrivit pe care sa-l urmeze.

Gigel ar fi dispus sa iasa din casa, sa-si viziteze toti prietenii si sa se intoarca inapoi acasa. Intre casele a 2 prieteni, intre casa lui si cea a unui prieten sau intre casa unui prieten si casa lui, el merge in linie dreapta, pe segmentul de dreapta ce le uneste. Asadar, drumul sau este format dintr-o succesiune de N+1 segmente. Gigel vre aca oricare 2 segmente din cadrul drumului sa nu se intersecteze (decat, cel mult, in capete).

Gasiti un drum potrivit pentru Gigel.

Date de intrare

Pe prima linie a fisierului de intrare melc.in se vor afla 2 numere reale, separate printr=-un spatiu: X si Y, reprezentand coordonatele casei lui Gigel. A doua linie contine numarul intreg N, reprezentand numarul de prieteni pe care Gigel trebuie sa ii viziteze. Pe urmatoarele N linii se afla cate 3 numere, separate prin cate un spatiu: X, Y si ID. ID va fi un numar intreg, reprezentand identificatorul unuia dintre prietenii lui Gigel. X si Y sunt 2 numere reale, reprezentand coordonatele casei prietenului Gigel identificat prin valoarea lui ID.

Date de iesire

In fisierul de iesire melc.out veti afisa N+2 linii: identificatorii prietenilor ale caror case le va vizita Gigel, in ordinea in care ii viziteaza. Incepeti cu identificatorul lui Gigel (care este numarul 0), continuati cu identificatorul primului prieten pe care il viziteaza s.a.m.d. Incheiati tot cu identificatorul lui Gigel. Daca nu exista solutie, afisati doar numarul -1.

Restrictii

  • 2 ≤ N ≤ 1000
  • -100 000 ≤ coordonatele X si Y ale oricarui punct ≤ 100 00
  • Coordonatele punctelor sunt date cu o precizie de cel mult 3 zecimale.
  • Identificatorii prietenilor lui Gigel sunt numere intregi distincte, cuprinse intre 1 si N.
  • Oricare 3 prieteni (inclusiv Gigel) nu au casele pe aceeasi linie dreapta.

Exemplu

melc.inmelc.out
0 0
3
3 3 1
6 0 2
6 2 3
0
1
3
2
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?