首页 > 代码库 > uva 1356 - Bridge(积分+二分)
uva 1356 - Bridge(积分+二分)
题目链接:uva 1356 - Bridge
题目大意:在一座长度为B的桥上建若干个塔,塔的间距不能超过D,塔的高度为H,塔之间的绳索形成全等的抛物线。绳索的总长度为L。问在建最少塔的情况下,绳索的最下段离地面的高度。
解题思路:贪心的思想求出最少情况下建立的塔数。
二分高度,然后用积分求出两塔之间绳索的长度。
C++ 积分#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
double f (double a, double x) {
double aa = a * a, xx = x * x;;
return (x * sqrt(aa + xx) + aa * log(fabs(x + sqrt(aa + xx)))) / 2;
}
double parabola_length (double w, double h) {
double a = 4 * h / (w * w);
double b = 1.0 / (2 * a);
return (f(b, w/2) - f(b, 0)) * 4 * a;
}
double bsearch (double l, double r, double d, double v) {
while (r - l > 1e-5) {
double mid = (r + l) / 2;
if (parabola_length(d, mid) < v)
l = mid;
else
r = mid;
}
return l;
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
int D, H, B, L;
scanf("%d%d%d%d", &D, &H, &B, &L);
int n = (B + D - 1) / D;
double d = B * 1.0 / n;
double l = L * 1.0 / n;
if (kcas > 1)
printf("\n");
printf("Case %d:\n%.2lf\n", kcas, (double)H - bsearch(0, H, d, l));
}
return 0;
}
C++ 辛普森#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
double A;
double f (double x) {
return sqrt (1 + 4 * A * A * x * x);
}
double simpson (double a, double b) {
double c = (a + b) / 2;
return (f(a) + 4*f(c) + f(b)) * (b-a) / 6;
}
double asr (double a, double b, double eps, double S) {
double c = (a + b) / 2;
double L = simpson(a, c), R = simpson(c, b);
if (fabs(L+R-S) <= eps * 15)
return L + R + (L + R - S) / 15;
return asr(a, c, eps/2, L) + asr(c, b, eps/2, R);
}
double asr (double a, double b, double eps) {
return asr(a, b, eps, simpson(a, b));
}
double parabola_length (double w, double h) {
A = 4 * h / (w * w);
return asr(0, w / 2, 1e-5) * 2;
}
double bsearch (double l, double r, double d, double v) {
while (r - l > 1e-5) {
double mid = (r + l) / 2;
if (parabola_length(d, mid) < v)
l = mid;
else
r = mid;
}
return l;
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
int D, H, B, L;
scanf("%d%d%d%d", &D, &H, &B, &L);
int n = (B + D - 1) / D;
double d = B * 1.0 / n;
double l = L * 1.0 / n;
if (kcas > 1)
printf("\n");
printf("Case %d:\n%.2lf\n", kcas, (double)H - bsearch(0, H, d, l));
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。