Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Duomenų failas: besmegeniai.in

Rezultatų failas: besmegeniai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Besmegeniai

Gal jūs ir nežinot, bet sniego seniai-besmegeniai labai mėgsta bendrauti. Deja, retas žmogus stabteli su jais pasišnekėti, apie gyvenimą arba sniegą, todėl besmegeniai dažniausiai bendrauja tarpusavy. Aišku, stovėdami ten, kur buvo nulipdyti, jie gali šnekėtis tik su pakankamai netoli esančiais besmegeniais. Tačiau naktys žiemą ilgos, ir besmegeniai nesibodi perduoti žodžius iš lūpų į lūpas. Šitaip jie gali bendrauti ir su toliau nulipdytais besmegeniais.

img

Nulipdytam besmegeniui visuomet labai rūpi, su kuriais kitais besmegeniais jis gali susisiekti (tiesiogiai, arba per "tarpinius" besmegenius). Parašykite programą, kuri tai nustatytų.

Pradiniai duomenys

Pirmoje pradinių duomenų faile įrašyti du sveikieji skaičiai: mieste nulipdytų besmegenių skaičius N, ir maksimalus bendravimo atstumas L - besmegeniai, kuriuos skiria daugiau negu L metrų, tiesiogiai bendrauti negali. (1\\leN,L\\le1000).

Sekančiose dviejose eilutėse įrašytas ką tik nulipdyto besmegenio vardas, bei sveikosios koordinatės plokštumoje (X, Y).

Likusiose failo eilutėse pateikiama informacija likusius N - 1 besmegenių: vardas, ir koordinatės ploštumoje (X_i,Y_i) metrais (žr. pavyzdį). Visų besmegenių vardai yra skirtingi. -10000\\leX_i, Y_i\\le10000.

Rezultatai

Į rezultatų failą programa turi įrašyti visus besmegenius abėcėlės tvarka, su kuriais tiesiogiai arba per "tarpinius" besmegenius gali bendrauti naujai nulipdytasis. Tokių visuomet bus bent vienas. (O jei kada nors pamatysite vienišą besmegenį, nepatingėkit nulipdyti jam draugą.)

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
4 10
Dovydas
0 0
Baltazaras
6 8
Kasparas
-7 9
Merkelis
14 3
 
Baltazaras
Merkelis
 Dovydas gali bendrauti tik su Baltazaru (tiesiogiai) bei Merkeliu (per Baltazarą).

Pastaba

Atstumas tarp taškų (A_x,A_y) ir (B_x,B_y) apibrėžiamas kaip šaknis iš atitinkamų koordinačių skirtumų kvadratų sumos (prisiminkit Pitagoro teoremą):

function atstumas(Ax, Ay, Bx, By : longint) : real;
begin
   atstumas := sqrt(sqr(Ax - Bx) + sqr(Ay - By));
end;

Dar geriau yra tiesiogiai naudotis Pitagoro teorema ir patikrinti sąlygą:

sqr(Ax - Bx) + sqr(Ay - By) <= sqr(L)

Tuomet neatliekamos operacijos su realiaisiais skaičiais, ir negali atsirasti apvalinimo paklaidų!