Slaloms

ID: slaloms
Grūtība: 3/5
Laika limits: 1

Uzdevums

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ā.

 

Ievaddati

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.

 

Izvaddati

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.

 

Piemērs

slaloms.datslaloms.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.datslaloms.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.datslaloms.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

 

Atsauces

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā
© 2001-2002 olimps! http://www.lio.lv/olimps/