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!
BemenetA 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.
KimenetAz egyetlen sorba a legrövidebb út hosszát kell kiírni, legalább 10-6 pontossággal.
Példa
Tesztadatok
CímkékA feladat forrása: http://codeforces.com/problemset/problem/30/D
Algoritmusok: rendezés, mohó algoritmus, eset szétválasztás
megoldás |
Programozás > Feladatok >
