[THUPC2022 初赛] 喵喵花園 题解

· · 题解

是我喜欢的计算几何！赛场上一边吃午饭一边写完的（

首先我们知道这 K 棵圣诞树均匀分割了整个凸多边形的边长，那么相邻两棵圣诞树在凸多边形边上的距离就是一定的（设为 dis）。我们选择一棵树观察，将其向顺时针方向挪动 dis，发现对于每一棵树，其后面一棵树来到了它先前所在的位置，整体也就回到了挪动前的状态。

我们定义 跳边 代表树挪到一条边的端点，然后前往下一条边的瞬间，那么由于所有树移动的距离恰好覆盖整个凸多边形的周长，发生的 跳边 次数和凸多边形拐角数目一样，也就是 N。

考虑模拟整个过程，钦定一棵树，一开始在凸多边形的某一个端点，然后向右挪 dis。期间我们可以求出其它所有点的位置，由此推出所有 跳边 的时间点。由于两次 跳边 之间，每个点都在一个线段之间移动，所以我们尝试用函数表示出这段时间的凸多边形面积，并求出最小值。

我们定义这 K 棵树所在位置为 t_1, t_2, ..., t_K，这 N 条边的长度为 s_1, s_2, ..., s_N，其中 s_1 代表的边连接 p_1 和 p_2，依次类推，同时默认 p_{N+1}=p_1。

在这个时间段的开始，每个点在凸多边形的周长上和 p_1 的距离（p_1 顺时针到达该点的距离）是确定的。我们可以按顺序枚举每个点，然后使用指针维护当前点所在的边。

假设第 i 个点落在了第 j 条边上，和 p_j 的距离为 d。那么我们考虑将这个点的坐标借助时间表示出来。我们不妨假设时间为 x，那么前面的距离将会扩大到 d+x，根据向量的知识，我们可以求出 \overrightarrow{p_jp_{j+1}} 的单位向量于距离相加，加上初始点 p_j，即：

t_i = p_j + \dfrac{\overrightarrow{p_jp_{j+1}}}{|\overrightarrow{p_jp_{j+1}}|} \times (d + x)

我们就成功使用时间表示了每个点的位置。

然后我们就可以使用叉积算出凸多边形的面积（具体而言，选择一个点向其余所有非相邻点连边，将凸多边形拆成若干个三角形，而向量叉积的结果的绝对值恰为其围成三角形面积的两倍），最终得到一个二次函数。那么我们只需要考虑这个时间段内二次函数的最小值就能解决问题。

最后把所有时间段的答案统计起来就完成了，复杂度为 O(NK + N^2)。如果在求出 跳边 时间点的同时存储对应点，就可以省去重新获取所有点所在边的位置的时间复杂度，使总复杂度降为 O(NK)。

代码中 KBs 维护了 kx + b。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;
struct KBs{
    double k, b;
    KBs(double k=0, double b=0)
        :k(k), b(b){}
    KBs operator + (const KBs x) const{
        return KBs(k + x.k, b + x.b);
    }
    KBs operator - (const KBs x) const{
        return KBs(k - x.k, b - x.b);
    }
    KBs operator * (const double p) const{
        return KBs(k * p, b * p);
    }
};
struct Point{
    KBs x, y;
    Point(KBs x = 0, KBs y = 0)
        :x(x), y(y){}
    Point operator + (const Point& p)const{
        return Point(x + p.x, y + p.y);
    }
    Point operator - (const Point& p)const{
        return Point(x - p.x, y - p.y);
    }
    Point operator * (const double k)const{
        return Point(x * k, y * k);
    }
    Point operator * (const KBs k)const{
        return Point(k * x.b, k * y.b);
    }
};
double sqr(double x){
    return x * x;
}
struct Segment{
    Point st, ed;
    Segment(Point st = Point(KBs(), KBs()), Point ed = Point(KBs(), KBs()))
        :st(st), ed(ed){}
    double len(){
        return sqrt(sqr(st.x.b - ed.x.b) + sqr(st.y.b - ed.y.b));
    }
    Point at(KBs k){
        return st + (ed - st) * k;
    }
};
struct Function{
    double a, b, c;
    Function(double a=0, double b=0, double c=0)
        :a(a), b(b), c(c){}
    Function operator + (const Function& f)const{
        return Function(a + f.a, b + f.b, c + f.c);
    }
    Function operator - (const Function& f)const{
        return Function(a - f.a, b - f.b, c - f.c);
    }
    double at(double x){
        return a * x * x + b * x + c;
    }
    double minn(double l, double r){
        if(a == 0)
            return min(at(l), at(r));
        // return 0.0;
        double mn = -1.0 * b / (2 * a);
        if(l <= mn && mn <= r)
            return min({at(l), at(r), at(mn)});
        return min(at(l), at(r));
    }
};
Point ps[1010];
Segment segs[1010];
int N, K;
int curr[1010];
double lens[1010];
double lenfnt[1010];
vector<pair<double, int> > vec;

Function KBsCross(KBs x, KBs y){
    return Function(x.k * y.k, x.k * y.b + x.b * y.k, x.b * y.b);
}
Function pointCross(Point x, Point y){
    return KBsCross(x.x, y.y) - KBsCross(x.y, y.x);
}

int main(){
    scanf("%d%d", &N, &K);
    for(int i=N; i>=1; i--)
        scanf("%lf %lf", &ps[i].x.b, &ps[i].y.b);
    ps[N+1] = ps[1];
    double C = 0;
    for(int i=1; i<=N; i++)
        segs[i] = Segment(ps[i], ps[i+1]), C += lens[i] = segs[i].len();
    segs[N+1] = segs[1];
    C /= K;
    double las = 0;
    int m = 1;
    curr[1] = 0;
    for(int i=1; i<=N; i++){
        las += lens[i];
        lenfnt[i] = lenfnt[i-1] + lens[i];
        while(las >= C && m != K)
            las -= C, curr[++m] = i;
        if(i == N)
            m = 1;
        else
            vec.emplace_back(las, m);
    }
    lens[N+1] = lens[1];
    vec.emplace_back(0, 1);
    vec.emplace_back(C, 1);
    sort(vec.begin(), vec.end());
    double ans = 1e18;
    for(int i=0; i<(int)vec.size()-1; i++){
        pair<double, int> pr = vec[i];
        curr[pr.second] ++;
        double L = pr.first, R = vec[i+1].first;
        vector<Point> plist(K + 2);
        for(int j=1; j<=K; j++){
            int id = curr[j];
            double y = (j-1) * C - lenfnt[id-1];
            KBs num(1.0 / lens[id], y / lens[id]);
            plist[j] = segs[id].at(num);
        }
        Function f;
        for(int i=1; i<=K; i++){
            int j = i % K + 1;
            f = f + pointCross(plist[i], plist[j]);
        }
        if(f.at(L) < 0) // 建议加上这个检查，防止凸多边形叉出来面积是个负数
            f.a *= -1, f.b *= -1, f.c *= -1;
        ans = min(ans, f.minn(L, R));
    }
    printf("%.12f", ans / 2);
    return 0;
}