P5916 题解

· · 题解

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

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

当然你还可以直接算出来距离。设该直线的解析式为 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);
    }
}