D. Хааны аялал

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жинхэнэ хаан болгон амьдралынхаа туршид дэлхийг эзлэх, "Codeforces World Final"-д түрүүлэх, буудлаганы тэмцээнээс ягаан баавгайг хожих, эзэнт гүрнээрээ аялах гэсэн зүйлсүүдийг хийх ёстой.

Хаан Копа эхний гурван зүйлсийг хийчихсэн. Одоо түүнд зөвхөн эзэнт гүрнээрээ аялах л үлдээд байна. Хаант улс бол тэгш өнцөгт координатын систем бүхий хязгааргүй том хавтгай юм. Эзэнт гүрэнд $(x_{1}, 0), (x_{2}, 0), ..., (x_{n}, 0)$ координаттай $n$ хот болон бас $(x_{n + 1}, y_{n + 1})$ координаттай нэг хот байдаг.

Хаан аялалаа $k$ дугаартай хотоос эхлэх ба таны даалгавар хаанд бүх хотоор дайрах хамгийн бага урттай замыг олж өгөх юм. Нэг хотоор $2$ удаа дайрахыг зөвшөөрнө. Хаан аялалаа аль ч хотод дуусгаж болно. Аль ч $2$ хотын хооронд өгөгдсөн цэгүүдийн хоорондох зайтай тэнцүү урттай шулуун зам бий. Аль ч $2$ хот нэг цэг дээр байрлахгүй.

Оролт

Эхний мөрөнд $n$ ба $k$ ($1 ≤ n ≤ 10^{5}, 1 ≤ k ≤ n + 1$) бүхэл тоонууд болох нийт хотын тоо болон аялалыг эхэлж буй хотын дугаар өгөгдөнө.

Дараагийн мөрөнд $n + 1$ ширхэг $x_{i}$ тоонууд өгөгдөнө.

Гурав дахь мөрөнд $y_{n + 1}$ өгөгдөнө. Бүх координатууд бүхэл бөгөөд $10^{6}$-ээс хэтрэхгүй. Аль ч $2$ хот давхцахгүй.

Гаралт

Хааны аялалын боломжит хамгийн бага уртыг хэвлэнэ. Таны хариултын үнэмлэхүй болон харьцангуй алдаа $10^{-6}$-аас бага байх ёстой.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
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
Сэтгэгдлүүдийг ачааллаж байна...