HDU 1071 The area 高斯消元擬合二次曲線+辛普森積分

問題步驟

1. 三點確定二次函數 y = ax² + bx + c，構造線性方程組高斯消元求係數
2. 兩點確定直線 y = kx + m
3. 計算曲線與直線圍成面積：∫[x1,x2] (f₁(x) - f₂(x)) dx
4. 辛普森公式數值積分：∫ ≈ h/3 [f(a)+f(b) + 4∑f(x_odd) + 2∑f(x_even)]

高斯消元模板

void Gauss(int cnt) {
    for (int i = 0; i < cnt; i++) {
        // 列主元選擇
        int k = i; double big = fabs(g[i][i]);
        for (int j = i+1; j < cnt; j++) if (fabs(g[j][i]) > big) { big = fabs(g[j][i]); k = j; }
        if (k != i) for (int j = 0; j <= cnt; j++) swap(g[i][j], g[k][j]);
        // 消元
        for (int j = i+1; j < cnt; j++)
            if (g[j][i]) {
                double tmp = -g[j][i] / g[i][i];
                for (int k = i; k <= cnt; k++) g[j][k] += tmp * g[i][k];
            }
    }
    // 回代
    for (int i = cnt-1; i >= 0; i--) {
        for (int j = i+1; j < cnt; j++) g[i][cnt] -= g[j][cnt] * g[i][j];
        g[i][cnt] /= g[i][i];
    }
}

辛普森積分

double simpson(double a, double b, int n) {
    double h = (b-a)/n, ans = f(a) + f(b);
    for (int i = 1; i < n; i += 2) ans += 4*f(a+i*h);
    for (int i = 2; i < n; i += 2) ans += 2*f(a+i*h);
    return ans * h / 3;
}

取 n=1000 足夠精度。注意直線兩點式：(x-x1)/(x2-x1)*(y2-y1)+y1。