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

Vezi solutiile trimise | Statistici

Melc

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.
Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

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, Gigel merge in linie dreapta, pe segmentul de dreapta ce le uneste. Asadar, drumul sau este format dintr-o succesiune de N+1 segmente. Gigel vrea ca 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
  • -200 000 ≤ coordonatele X si Y ale oricarui punct ≤ 200 000
  • 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?

remote content