UVA1356 Bridge

Latex渲染失败点我

前置芝士 Simpson 公式

我看到题解中没有一篇认真讲过辛普森公式，于是就来水一篇题解。

基本思想

将函数近似看做二次函数

由于这个原因，这个公式及其的简单且不精确。

公式推导

$$\int_a^b f(x) dx$$

上方是最最基础的微积分求面积的公式；

刚刚的思想中讲到了思路是将 $f(x)$ 看做 $ax^2 + bx + c$ ,于是有:

$$= \int_a^b (Ax^2+Bx+C)dx$$

$$\approx \int_a^b (\frac{Ax^2}{3} + \frac{Bx}{2} + \frac{C}{1})$$

$$= \frac{Ab^3}{3} - \frac{Aa^3}{3} + \frac{Bb ^2}{2} - \frac{Ba ^ 2}{2} + Cb - Ca$$

$$= \frac{2Ab^3 - 2Aa^3 + 3Bb^2 - 3Ba^2 + 6b - 6CaC}{6}$$

$$= \frac{2A(a^3 - b^3) +3B(b^2 - a^2) + 6C(b-a)}{6}$$

$$= \frac{2A(b-a)(a^2 + b^2 + ab) + 3B(a + b)(b-a) + 6C(b-a)}{6}$$

$$= \frac{(b-a)(2Aa^2 + 2Ab^2 + 2Aab + 3Ba + 3Bb + 6C)}{6}$$

$$= (b-a)\frac{(Aa^2 + Ba + C) + (Ab^2 + Bb + C) + (Aa^2 + Ab^2 + 2Ba + 2Bb + 2Aab + 4C)}{6}$$

$$= (b-a)\frac{f(a) + f(b) + 4(\frac{Aa^2}{4} + \frac{Ab^2}{4} + \frac{Ba}{2} + \frac{Bb}{2} + \frac{2Aab}{4} + C)}{6}$$

$$= (b-a)\frac{f(a) + f(b) + 4(\frac{Aa^2 + Aab}{4} + \frac{Ab^2 + Aab}{4} + \frac{Ba + Bb}{2} + C)}{6}$$

$$= (b-a)\frac{f(a) + f(b) + 4(A\frac{a(a + b)}{4} + A\frac{b(a + b)}{4} + B\frac{a +b}{2} + C)}{6}$$

$$= (b-a)\frac{f(a) + f(b) + 4(A\frac{(a + b) ^ 2}{4} + B\frac{a +b}{2} + C)}{6}$$

$$= (b-a)\frac{f(a) + f(b) + 4f(\frac{a + b}{2})}{6}$$

所以，我们得到：

$$\int_a^b f(x) dx \approx (b-a)\frac{f(a) + f(b) + 4f(\frac{a + b}{2})}{6}$$

处理精度问题

为了控制精度，以及不必要的问题，保留两位小数时 eps 一般取 $10^{-6} \sim 10^{-8}$

有了 Simpson 公式，一个自然的想法是把积分区间拆成多个小区间后求和。

但是分成区间的个数和长度因积分区间和精度要求甚至被积函数而异。

换句话说，分的区间数太少不满足精度要求，太多了会 TLE 。

「自适应」就是求积分时能够自动控制切割的区间大小和长度，使精度能满足要求。

具体地： solve(l , r) 表示求 $\int_r^l f(x)dx$

1. 取 mid = l+r >> 1;
2. 用 Simpson 公式近似计算 $f(x)$ 在区间 $[l,mid]$ 和区间 $[mid,r]$ 内的积分，分别为 $l_s$ 和 $r_s$ ，及 $[l,r]$ 的近似积分 $sum$ ;
3. 如果 $l_s + r_s$ 与 $sum$ 的误差允许(即在 eps 之内)，则返回 $sum$ ;
4. 否则递归 solve(l , mid) 和 solve(mid , r) ，返回这两个递归计算结果的和;

摘自 这篇博文。

分析

其实电线杆的数量可以贪心，即为 $\lceil\frac{n}{d}\rceil$, 然后使用弧长公式加辛普森乱搞就出来了

公式$$f(x) = \sqrt{1 + 4a^2x2}$$

参考代码

#include <bits/stdc++.h>
using namespace std;

double a;

double Function (double x) {
    return sqrt(1 + 4 * a * a * x * x);
}

double Solve (double l , double r) {
    double mid = (l + r) / 2;
    return (Function(l) + Function(r) + Function(mid) * 4) * (r - l) / 6;
}

double Simpson (double l , double r , double eps , double res) {
    double mid = (l + r) / 2;
    double x1 = Solve(l , mid) , x2 = Solve(mid , r);
    if(abs(x1 + x2 - res) <= 15 * eps) return x1 + x2 + (x1 + x2 - res) / 15;
    else return Simpson(l , mid , eps / 2 , x1) + Simpson(mid , r , eps / 2 , x2);
}

const double eps = 1e-9;

double D , H , B , L , W;
int T;

double Check(double x) {
    a = 4 * x / (W * W);
    return Simpson(0 , W / 2 , eps , Solve(0 , W / 2)) * 2;
}


int main() {
    scanf("%d" ,&T);
    for(int i = 1; i <= T; i++) {
        cin >> D >> H >> B >> L;
        double l = 0 , r = H;
        int n = (B - 1) / D + 1;
        W = B / n;
        L = L / n;
        while(r > l + eps) {
            double Mid = (l + r) / 2;
            if(Check(Mid) <= L) {
                l = Mid;
            }
            else r = Mid;
        }
        printf("Case %d:\n%.2lf\n" ,i , H - l);
        if(i != T) {
        	printf("\n");
		}
    }
    return 0;
}