首页 > 代码库 > UVA 1356 - Bridge(自适应辛普森)
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。