A. Falfa with Polygon

Solution

考虑我们选出的凸包，从1到n看就只有一条边是从较大编号连到较小编号，考虑dp出$f_k[i][j]f\_\{k\}[i][j]$表示长度为k的从$ii$开始到$jj$结束的子序列的最大长度，其与i、j两点长度的和就是凸包的周长。
写出$ff$的转移方程如下

$\{max,+\}\backslash \{max,+\backslash \}$这种运算可以利用矩阵快速幂加速递推过程，运算方式与矩阵乘法类似，满足结合律。但直接这样做复杂度是$O(n^3\log k)O(n^3\backslash log\; k)$的。
$ff$满足四边形不等式，设$f[i][j]f[i][j]$的决策点为$p[i][j]p[i][j]$，因此有

枚举长度从小到大进行转移，维护决策点$p[i][j]p[i][j]$和答案$f[i][j]f[i][j]$，矩阵乘法的复杂度降为$O(n^2)O(n^2)$。
总时间复杂度$O(n^2\log k)O(n^2\backslash log\; k)$。

struct Matrix {
    int n, m;
    vector<vector<double> >a;
    Matrix() {}
    Matrix(int n, int m): n(n), m(m) { a.resize(n, vector<double>(m, 0)); }
    Matrix operator *(const Matrix &s)const {
        Matrix ans = Matrix(n, s.m);
        // for (int i = 0; i < n; ++i)
        //     for (int j = 0; j < n; ++j)
        //         for (int k = 0; k < n; ++k)
        //             ans.a[i][j] = max(ans.a[i][j], a[i][k] + s.a[k][j]);
        vector<vector<int> >p(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            p[i][i] = i;
        }
        for (int len = 1; len <= n; ++len) {
            for (int i = 0; i + len < n; ++i) {
                for (int j = i + len, k = j ? p[i][j - 1] : 0; k <= p[i + 1][j]; ++k) {
                    if (ans.a[i][j] < a[i][k] + s.a[k][j]) {
                        ans.a[i][j] = a[i][k] + s.a[k][j];
                        p[i][j] = k;
                    }
                }
            }
        }
        return ans;
    }
};
double x[N], y[N];
Matrix ksm(Matrix base, ll b) {
    Matrix ans = Matrix(base.n, base.m);
    for (int i = 0; i < base.n; ++i)ans.a[i][i] = 0;
    for (; b; b >>= 1, base = base * base)
        if (b & 1)ans = ans * base;
    return ans;
}

int main() {
    int n = fast_IO::read(), k = fast_IO::read();
    for (int i = 0; i < n; ++i)
        scanf("%lf%lf", x + i, y + i);
    Matrix base = Matrix(n, n);
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            base.a[i][j] = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
    Matrix ans = ksm(base, k - 1);
    double maxn = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            maxn = max(maxn, ans.a[i][j] + sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2)));
    printf("%.10f", maxn);
    return 0;
}