Programozás‎ > ‎Feladatok‎ > ‎

A király problémája

Minden igazi király végiglátogatja birodalma városait, miután meghódította a világot. Programozó Király országában elég speciálisan helyezkednek el a városok, egy végtelen koordináta-sík egész koordinátájú pontjaiban, melyek alakja:
(x1, 0), (x2, 0), ..., (xN, 0), és (xN + 1, yN + 1).
(Tehát egyetlen olyan város van, amelyik nem az X tengelyen található.)
A király a K sorszámú városból indul, és úgy szeretné  végiglátogatni a városokat, hogy az út hossza minimális legyen. Tetszőleges sorrendben haladhat, egy városon többször is átutazhat, és bármely két város között létezik egyenes út, aminek hossza a városok euklideszi távolsága.

Feladat

Írjunk programot, ami kiszámolja a lehetséges legrövidebb út hosszát!  

Bemenet

A bemenet első sora az N és K értékét adja meg. (1 <= N <= 105, 1 <= K <= N+1) N+1 város van, és a K sorszámúból indul a király.
A második sor N+1 egész számot tartalmaz, az xi értékeket. A harmadik sor yN+1 értékét adja meg. A koordináták egész számok, abszolút értékük legfeljebb 106.

Kimenet

Az egyetlen sorba a legrövidebb út hosszát kell kiírni, legalább 10-6 pontossággal.

Példa

Bemenet  Kimenet
3 1
0 1 2 1
1
3.41421356237309490000

3 1
1 0 2 1
1
3.82842712474619030000
4 5
0 5 -1 -5 2
3
14.24264068711928400000

Tesztadatok

A lent linkelt oldal 132 tesztesetet vizsgál.
Ebből az első tíz: kiraly-teszt.txt

Címkék

Algoritmusok: rendezés, mohó algoritmus, eset szétválasztás

megoldás