自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:15:36，当前版本为作者最后更新于2023-03-27 19:04:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意就是给定点集让你求一条直线，最小化点到直线距离的平方和。

然后这其实就是总体最小二乘法拟合直线，所以做完了（雾）。

当然你还可以直接算出来距离。设该直线的解析式为 $y=kx+b$，那么得到结果为：

$$\begin{aligned} &\dfrac{\sum_i(kx_i+b-y_i)^2}{k^2+1}\\ =&\dfrac{\sum_ik^2x_i^2+b^2+y_i^2+2kbx_i-2kx_iy_i-2by_i}{k^2+1}\\ =&\dfrac{(\sum_ix_i^2)k^2+nb^2+(\sum_iy_i^2)+2((\sum_ix_i)kb-(\sum_ix_iy_i)k-(\sum_iy_i)b)}{k^2+1}\\ \end{aligned} $$

然后里面一车都是定值，预处理 $\sum_ix_i^2$，$\sum_iy_i^2$，$\sum_ix_i$，$\sum_iy_i$，$\sum_ix_iy_i$ 就可以做了。$k,b$ 直接三分。

真的有勇士要偏导数硬算我觉得也不是不行

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN = 1e5 + 10;
const ld eps = 1e-7;
const ld pi = acos(-1);

int t, n; ll a, b, c;

ll x, y, sx, sy, sxx, syy, sxy;

inline 
ld f(ld k, ld b) {
	return (sxx * k * k + n * b * b + syy + 2 * (sx * k * b - sxy * k - sy * b)) / (k * k + 1);
}

inline 
ld calc(ld k) {
	ld l = -1e9, r = 1e9, p, q;
	for (; r - l > eps; f(k, p = l + (r - l) / 3) > f(k, q = r - (r - l) / 3) ? l = p : r = q);
	return f(k, l);
}

inline 
ld solve() {
	ld l = -1e9, r = 1e9, p, q;
	for (; r - l > eps; calc(p = l + (r - l) / 3) > calc(q = r - (r - l) / 3) ? l = p : r = q);
	return calc(l);
}

int main() {
	scanf("%d", &t);
    for (int p = 1; p <= t; p++) {
    	scanf("%d%lld%lld%lld%lld%lld", &n, &x, &y, &a, &b, &c);
    	sx = sy = sxx = syy = sxy = 0;
    	for (int i = 1; i <= n; i++) {
    		sx += x, sy += y, sxx += x * x, syy += y * y, sxy += x * y;
    		x = (a * x * x + b * x + c) % 107, y = (a * y * y + b * y + c) % 107;
		}
		printf("Case %d: %.5Lf\n", p, solve() * pi / n);
	}
}