题目分析
本题要求在给定的凸 $N$ 边形边界上均匀放置 $K$ 棵圣诞树，形成一个凸 $K$ 边形，使得这个 $K$ 边形的面积尽可能小。

关键观察

• 树木必须均匀分布在多边形周长上，相邻树之间的弧长相等
• 需要找到最优的起始位置，使得形成的凸 $K$ 边形面积最小
• 问题转化为在连续弧长参数空间中寻找最优解

算法思路
核心思想：参数化搜索 + 函数化几何计算

数学模型

1. 周长参数化

• 总周长 $C = \sum_{i=0}^{n-1} d_i$，其中 $d_i$ 是第 $i$ 条边的长度
• 相邻树间距 $f = C / K$

2. 关键点理论 最优解必然出现在某些"关键点"，这些点包括：

• 弧长参数为 $0$ 和 $f$ 的位置
• 多边形顶点在弧长参数空间中的投影位置

算法流程

1. 预处理计算

// 计算总周长和边长
for (int i = 0; i < n; i++) {
    c += (d[i] = distance(s[i], s[(i + 1) % n]));
}
f = c / k;  // 树间距

2. 关键点收集

vector<ldb> v;
v.push_back(0);
v.push_back(f);

for (int i = 0; i < n; i++) {
    cnt += d[i];
    v.push_back(cnt - floor(cnt / f) * f);  // 顶点在参数空间的投影
}
sort(v.begin(), v.end());

3. 函数化几何计算 使用 func 类表示参数化的坐标函数：

struct func {
    ldb a, b, c;  // 表示 a*x² + b*x + c
    // 支持函数运算：加减乘除
};

struct po2 {
    func x, y;  // 参数化的点坐标
};

4. 面积计算与优化

ldb calc(ldb l, ldb r) {
    // 在区间 [l, r] 内计算最小面积
    ldb x = (l + r) / 2;
    
    // 计算 K 个树的位置
    for (int i = 0, j = 0; i < k; i++) {
        while (tmp + d[j] <= x + i * f - 1e-10)
            tmp += d[j++];
        
        // 线性插值计算树的位置函数
        p[i].x = func(0, (s[j+1].x - s[j].x)/d[j], 
                      s[j].x + (i*f - tmp)/d[j]*(s[j+1].x - s[j].x));
        p[i].y = func(0, (s[j+1].y - s[j].y)/d[j],
                      s[j].y + (i*f - tmp)/d[j]*(s[j+1].y - s[j].y));
    }
    
    // 计算多边形面积函数
    func area;
    for (int i = 0; i < k; i++) {
        area = area + (p[i].x * p[(i+1)%k].y - p[i].y * p[(i+1)%k].x) / 2;
    }
    
    // 在区间内求最小值
    return area.get_min(l, r);
}

关键技巧

1. 函数化计算

• 将坐标表示为弧长参数的线性函数
• 面积成为弧长参数的二次函数
• 利用函数运算直接处理几何关系

2. 区间划分优化

• 只在关键点划分的区间内搜索
• 每个区间内面积函数是简单的二次函数
• 使用 get_min 方法快速找到区间最小值

3. 数值稳定性

while (x < 0) x += f;
while (x >= f) x -= f;  // 保持参数在 [0, f) 范围内

复杂度分析

时间复杂度：$O(nk + n\log n)$

• 预处理：$O(n)$
• 关键点排序：$O(n\log n)$
• 每个区间计算：$O(k)$，共 $O(n)$ 个区间

空间复杂度：$O(n + k)$

正确性证明

1. 均匀分布：通过弧长参数化保证树木均匀分布
2. 凸性保持：在凸多边形边界上均匀取点形成的多边形仍是凸的
3. 最优性：关键点包含了所有可能的极值点位置
4. 数值精度：使用 long double 和高精度比较保证 $10^{-8}$ 精度要求

样例验证

样例1：

输入：5 4
顶点：5个
输出：1.9892766953

算法正确找到最优起始位置，形成面积最小的四边形。

样例2：

输入：3 3  
顶点：三角形
输出：0.1226170434

在三角形边界上均匀取三点形成的小三角形面积。

该算法通过巧妙的参数化方法和函数化计算，高效解决了连续优化问题，在大数据范围内仍能保持良好性能。