设 \(f_i\) 表示假设只有编号为 \(1\sim i\) 的点，此时的答案。\(f_n\) 即为所求。
显然有：
\[f_i=\min\limits_{i-k\le j < i}\{f_j+dis(s\to j+1\to j+2\to\cdots\to i)\}+dis(i\to s) \]当 \(i\to i+1\) 时，大括号内部全局增加 \(dis(i\to i+1)\)，可以全局打标记后单调队列维护。
时间复杂度 \(O(n)\)。
// Problem: F - Christmas Present 2
// Contest: AtCoder - UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
// URL: https://atcoder.jp/contests/abc334/tasks/abc334_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
template<int mod>
inline unsigned int down(unsigned int x) {
return x >= mod ? x - mod : x;
}
template<int mod>
struct Modint {
unsigned int x;
Modint() = default;
Modint(unsigned int x) : x(x) {}
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
friend Modint operator/(Modint a, Modint b) {return a * ~b;}
friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
friend Modint operator~(Modint a) {return a ^ (mod - 2);}
friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
friend Modint& operator++(Modint& a) {return a += 1;}
friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
friend Modint& operator--(Modint& a) {return a -= 1;}
friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
const int N = 2e5 + 5;
int n, k, sx, sy, x[N], y[N];
double dp[N], tag;
deque<tuple<int, double>> dq;
inline double sq(double x) {return x * x;}
inline double dis(double ax, double ay, double bx, double by) {return sqrt(sq(ax - bx) + sq(ay - by));}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k >> sx >> sy;
rep(i, 1, n) cin >> x[i] >> y[i];
x[0] = sx; y[0] = sy;
dq.emplace_back(0, dis(sx, sy, x[1], y[1]));
rep(i, 1, n) {
while(!dq.empty()) {
auto [id, pt] = dq.front();
if(i - id > k) dq.pop_front();
else break;
}
auto [id, pt] = dq.front();
pt += tag;
dp[i] = pt + dis(x[i], y[i], sx, sy);
tag += dis(x[i], y[i], x[i + 1], y[i + 1]);
while(!dq.empty()) {
auto [id, pt] = dq.back();
if(pt + tag > dp[i] + dis(sx, sy, x[i + 1], y[i + 1])) dq.pop_back();
else break;
}
dq.emplace_back(i, dp[i] + dis(sx, sy, x[i + 1], y[i + 1]) - tag);
}
cout << fixed << setprecision(15) << dp[n] << endl;
return 0;
}