Here, we will simply denote by “house \(i\)” the house of child \(i\). For each \(1\leq i < N\), there are two possible paths after giving a present to child \(i\) and before giving one for child \((i+1)\):

• directly travel from house \(i\) to house \((i+1)\); or
• go back to Santa’s house from house \(i\), and then head travel toward house \((i+1)\).

Let \(t_1,t_2,\dots,t_l\) be the sequence of the indices \(i\) for which the latter move is chosen, preceded by \(0\) and succeeded by \(N\) for convenience. The constraint that Santa can hold at most \(K\) presents means \(t_{j+1}-t_j <= K\) for all \(1 \leq j < l\). Thus, denoting by \(d_i\) the difference of the distances of the latter travel from the former, the problem can be boiled down to the following:

• You are given a sequence of real numbers \(d_1,d_2,\dots,d_{N-1}\). You can choose some number of terms so that no two terms are distant by more than \(K\), find the minimum sum of the chosen terms.

We use DP (Dynamic Programming) to solve it. Letting \(\mathrm{dp}[i]=\) the minimum sum of the chosen terms when choosing the \(i\)-th term and those in the first \(i\) terms so that no terms are distant by more than \(K\), one can find \(\mathrm{dp}[i]\) basically based on the minimum value of \(\mathrm{dp}[i-K], \mathrm{dp}[i-K+1],\dots, \mathrm{dp}[i-1]\), so one can use a segment tree or the sliding window technique to solve this problem in a total of \(O(N \log N)\) or \(O(N)\) time.

Sample code (C++):

#include <bits/stdc++.h>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

using ll = long long;

double dist(int x1, int y1, int x2, int y2) {
    int dx = x2 - x1;
    int dy = y2 - y1;
    return sqrt((ll) dx * dx + (ll) dy * dy);
}

using S = double;

S op(S a, S b) { return min(a, b); }

S e() { return 1e18; }

int main() {
    int n, k, sx, sy;
    cin >> n >> k >> sx >> sy;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    x.push_back(sx), y.push_back(sy);
    double ans = dist(sx, sy, x[0], y[0]);
    vector<double> d(n);
    for (int i = 0; i < n; i++) {
        double dir = dist(x[i], y[i], x[i + 1], y[i + 1]);
        double ret = dist(x[i], y[i], sx, sy) + dist(sx, sy, x[i + 1], y[i + 1]);
        ans += dir;
        d[i] = ret - dir;
    }
    segtree<S, op, e> dp(n + 1);
    dp.set(0, 0);
    for (int i = 1; i <= n; i++) {
        dp.set(i, dp.prod(max(0, i - k), i) + d[i - 1]);
    }
    ans += dp.get(n);
    cout << fixed << setprecision(15) << ans << endl;
}