自动搬运

查看原文

来自洛谷，原作者为

	tiger2005 Failure, as usual.

搬运于2025-08-24 22:36:58，当前版本为作者最后更新于2022-04-04 12:09:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

首先我们知道这 $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;
}