- Pradinių duomenų failas:
- salos.in
- Rezultatų failas:
- salos.out
- Laiko apribojimas:
- 2 s.
- Atminties apribojimas:
- 16 Mb.
Užduotis
Gimimo dienos proga Aleksas gavo didžiausią dovaną savo gyvenime – oro balioną! Savo balioną jis pavadino „Baleksu“ ir išsyk jį pamilo. Ruošdamasis kelionei aplink pasaulį, Aleksas vis daugiau ir daugiau laiko praleisdavo ore. Deja, paskutinio skrydžio metu netikėtai pakilo smarkus vėjas ir nunešė oro balioną į jūrą. Aleksas suvaldė „Baleksą“ ir sugebėjo nusileisti saloje, tačiau pakilti su balionu jau nebepavyktų.
Pasinaudojęs GPS imtuvu, Aleksas nustatė, kad netoliese yra kitų salų, o pro vieną iš jų nuolatos praplaukia krovininiai laivai. Kadangi ten jam pavyktų prisišaukti pagalbos, Aleksas ketina nuplaukti iki tos salos, sustodamas pailsėti tarpinėse salose. Tačiau Aleksas nėra olimpinis plaukikas, todėl jis nori pasirinkti tokį kelią per salas, kad ilgiausias be poilsio nuplauktas atstumas būtų kuo trumpesnis.
Tarp dviejų salų Aleksas gali plaukti tik tiesia linija, jungiančia tų salų centrus.
Pradiniai duomenys
Pirmoje pradinių duomenų failo eilutėje įrašyti trys sveikieji skaičiai N, A ir B (1 <= N <= 1000, 1 <= A, B <= N; A!= B). N yra salų skaičius, visos salos sunumeruotos nuo 1 iki N. A yra salos, kurioje Aleksas nusileido, o B – salos, į kurią jis nori patekti, numeriai.
Tolesnėse N eilučių pateikta informacija apie salas. i-ojoje iš šių eilučių įrašyti trys sveiki skaičiai: i-osios salos centro koordinatės \(x_{i}\) ir \(y_{i}\) (–10000 <= \(x_{i}\), \(y_{i}\) <= 10000), bei spindulys \(r_{i}\) (0 < r <= 1000). Salos nesiliečia, nesikerta ir nėra viena kitoje.
Rezultatai
Pirmoje rezultatų failo eilutėje turi būti įrašytas salų, kurias plaukdamas aplankys Aleksas, skaičius. Antroje eilutėje – tarpais atskirti salų, kurias Aleksas aplankys, numeriai. Ta pati sala neturėtų būti aplankyta kelis kartus. Linija, jungianti dviejų iš eilės einančių salų centrus neturi kirsti ar liesti kitos salos. Jei yra keli galimi sprendiniai, programa turi pateikti bet kurį.
Pavyzdžiai
| Pradiniai duomenys | Rezultatai | Paaiškinimas |
|---|---|---|
4 2 3 -3 1 1 -8 -4 2 8 0 2 1 -3 1 |
4 2 1 4 3 |
 Atkarpa 4-3 yra ilgiausia šiame kelyje; visuose kituose galimuose keliuose ilgiausia atkarpa, kuria plaukiama be poilsio, būtų ilgesnė; |
8 1 6 -6 0 2 -1 -10 2 20 4 6 8 8 1 -10 8 1 6 0 2 0 10 2 -5 5 1 |
5 1 8 7 4 6 |
 Ilgiausios atkarpos yra 7-4 ir 4-6 (abi vienodo ilgio). |