当前位置: 代码迷 >> 综合 >> UVA1356 Bridge (微积分 + 自适应辛普森法)
  详细解决方案

UVA1356 Bridge (微积分 + 自适应辛普森法)

热度:108   发布时间:2023-11-21 11:58:06.0

关键之处就在与一句话:

在(a, b)上可导的函数f(x)的弧长就g(x) = sqrt(1 + f'(x) ^ 2)在(a, b)上的定积分

所以说,题中的弧线明显为抛物线,那么它的长度就很可做了

然而你求的是深度……

没关系,假设深度depth和弧长L有一个函数L = h(depth),这个函数明显是单调增的

所以就可以二分答案

code:

#include <bits/stdc++.h>
#define EPS 1e-5
using namespace std;template <typename T> inline void read(T &x) {int c = getchar();bool f = false;for (x = 0; !isdigit(c); c = getchar()) {if (c == '-') {f = true;}}for (; isdigit(c); c = getchar()) {x = x * 10 + c - '0';}if (f) {x = -x;}
}#define Debug(...) fprintf(stderr, __VA_ARGS__)
//#define LOCALdouble A;double F(double x) {//the initial functionreturn sqrt(1 + 4 * A * A * x * x); 
}double calc(double a, double b) {double c = a + (b - a) / 2;return (F(a) + 4 * F(c) + F(b)) * (b - a) / 6.0000;
}double asr(double a, double b, double c, double eps, double Border) {double L = calc(a, c), R = calc(c, b);if(fabs(L + R - Border) <= 15 * eps) return L + R + (L + R - Border) / 15.0000;return asr(a, c, a + (c - a) / 2, eps / 2, L) + asr(c, b, (b - c) / 2 + c, eps / 2, R);
}double Simpson(double a, double b, double eps) {return asr(a, b, a + (b - a) / 2, eps, calc(a, b));
}int T, D, H, B, L;signed main() {read(T);for(int i = 1; i <= T; i++) {read(D), read(H), read(B), read(L);int n = (B + D - 1) / D;double stdD = (double) B * 1.000 / n;double stdL = (double) L * 1.000 / n;double l = 0.00000, r = (double) H;while(r - l > EPS) {double mid = (r - l) / 2 + l;A = 4 * mid / stdD / stdD;if(Simpson(0, stdD / 2, 1e-5) * 2 < stdL) l = mid;else r = mid;}printf("Case %d:\n%.2lf\n", i, H - l);if(i != T) puts("");}
#ifdef LOCALDebug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endifreturn 0;
}

  相关解决方案