UVA 1356 - Bridge(自适应辛普森)

UVA 1356 - Bridge

题意：一个桥长为B，桥上建电线杆。杆高为H，两杆之间距离不超过D。电线杆总长为L，杆子都是等距的，如今建最少的电线杆。问这时候电线离地面高度是多少

思路：二分高度，求出电线长，推断长度够不够就可以。那么问题就变成怎么求弧长

求弧长公式为∫w/201+(f′(x)2)−−−−−−−−−−√，

建立坐标系使得f(x)=ax2,带入点(w/2,
h)求出a。得到方程

那么问题就变成怎么求这个积分了

利用辛普森自适应法。去求就可以

代码：

#include <cstdio>

#include <cstring>

#include <cmath>

const double eps = 1e-8;

int t;

double d, h, b, l, m, w;

inline double F(double x) {

    double a = 4 * m / w / w;

    return sqrt(1 + 4 * a * a * x * x);

}

inline double simpson(double fa, double fb, double fc, double a, double c) {

    return (fa + 4 * fb + fc) * (c - a) / 6;

}

double asr(double a, double b, double c, double esp, double A, double fa, double fb, double fc) {

    double ab = (a + b) / 2, bc = (b + c) / 2;

    double fab = F(ab), fbc = F(bc);

    double L = simpson(fa, fab, fc, a, b), R = simpson(fb, fbc, fc, b, c);

    if (fabs(L + R - A) <= 15 * eps) return L + R + (L + R - A) / 15.0;

    return asr(a, ab, b, esp / 2, L, fa, fab, fb) + asr(b, bc, c, esp / 2, R, fb, fbc, fc);

}

double asr(double a, double c, double eps) {

    double b = (a + c) / 2;

    double fa = F(a), fb = F(b), fc = F(c);

    return asr(a, b, c, eps, simpson(fa, fb, fc, a, c), fa, fb, fc);

}

int main() {

    int cas = 0;

    scanf("%d", &t);

    while (t--) {

	scanf("%lf%lf%lf%lf", &d, &h, &b, &l);

	double n = ceil(b / d);

	l = l / n; w = b / n;

	double x = 0, y = h;

	while (fabs(x - y) > eps) {

	    m = (x + y) / 2;

	    if (2 * asr(0, w / 2, eps) < l) x = m;

	    else y = m;

	}

	printf("Case %d:\n%.2lf\n", ++cas, h - x);

	if (t) printf("\n");

    }

    return 0;

}