Lai uzvarētu slēpošanas slaloma sacensībās, sportistam slaloma trase jāveic pa visīsāko maršrutu. Naktī pirms sacensībām sportists ir ķēries pie trases kartes izpētes.
Trases sākuma un beigu punkti ir apzīmēti ar diviem punkti plaknē, savukārt vārti, kuriem sportistam jāizbrauc cauri, ir apzīmēti ar taisnes nogriežņiem, kas paralēli koordinātu x asij. Skaitļu virkne, ko veido trases sākuma punkta y koordināta, visu vārtu to izbraukšanas secībā koordinātas un beigu punkta y koordinata, ir stingri dilstoša skaitļu virkne.
Jebkura sportista maršruts sākas trases sākuma punktā, beidzas trases beigu punktā un sastāv no taisnes nogriežņu virknes. Diviem pēc kārtas sekojošiem nogriežņiem viens galapunkts ir kopīgs un atrodas uz nogriežņa, kas apzīmē vārtus. Katrs maršrutā ietilpstošais nogrieznis savieno divus, pēc kārtas sekojošus, vārtus. Trases sākuma punkts ir maršruta pirmā nogriežņa galapunkts, bet trases beigu punkts ir maršruta pēdējā nogriežņa galapunkts.
Uzrakstiet programmu, kas aprēķina īsākā maršruta garumu un nosaka, kura no dotajām atbildēm ir vistuvāk precīzajam atrisinājumam! "Vistuvāk" nozīmē, ka, ja visām dotajām vērtībām tiek aprēķināta starpība (pēc moduļa) starp šo doto un jūsu atrasto atbildi, tad izvēlētajai atbildei šī starpība ir vismazākā.
Teksta faila slaloms.dat pirmajā rindā dota naturāla skaitļa N (vārtu skaits,1 ≤N≤5000) vērtība.
Faila otrajā rindā dotas trases sākuma punkta koordinātas XS un YS, kas atdalītas ar tukšumsimbolu.
Katrā no nākošajām N faila rindām dots pa vienu vārtu aprakstam - trīs veselu skaitļu X1,X2 un Y vērtības, kas atdalītas ar tukšumsimboliem. Zināms, ka X1<X2 un ka šis pieraksts nozīmē, ka šiem vārtiem atbilst nogrieznis ar galapunktiem punktos (X1,Y) un (X2,Y). Vārti ir doti tādā secībā, kā sportistam tie jāizbrauc.
Faila nākošajā rindā dotas trases beigu punkta koordinātas XC un YC, kas atdalītas ar tukšumsimbolu.
Neviena punkta neviena koordināta pēc absolūtās vērtības nepārsniedz 15000.
Tālāk failā seko 100 rindas, kur katrā no tām dots pa vienam atšķirīgam reālam skaitlim - iespējamam dotā uzdevuma atrisinājumam.
Teksta faila slaloms.rez vienīgajā rindā jāizvada naturāls skaitlis - tās atbildes numurs pēc kārtas, kura ir vistuvāk precīzajam īsākā maršruta garumam.
| slaloms.dat | slaloms.rez |
2 4 4 2 4 3 3 7 2 6 1 3.8275 3.8278 3.8281 3.8284 ... (vēl 96 rindas) |
4 |
| slaloms.dat | slaloms.rez |
3 5 4 2 4 2 5 7 1 2 4 0 5 -2 7.3006 7.3009 7.3012 7.3015 ... (vēl 96 rindas) |
1 |
| slaloms.dat | slaloms.rez |
5 0 10 -4 -2 9 -8 -4 8 -6 -3 6 -8 -6 4 -10 -9 3 0 1 20.7621 20.7624 20.7627 20.7630 ... (vēl 96 rindas) |
3 |