当前位置：首页 > article >正文

AcWing 1510：楼梯 ← 浮点数二分

article 2025/1/11 20:57:06

【题目来源】
http://poj.org/problem?id=2507
https://www.acwing.com/problem/content/1512/

【题目描述】
一个街道两侧有两栋楼，现在有如图所示两楼梯 x，y。
两个楼梯分别如图放置。
已知两个楼梯的长度和他们交点离地面的高度，求两栋楼之间的距离。

【输入格式】
一行三个实数，分别表示 x，y，c。

【输出格式】
输出共包含 1 行。
即所求的两栋楼之间的距离，保留三位小数。

【数据说明】
0<a，b，c<2500
保证数据合法。

【输入样例】
30 40 10

【输出样例】
26.033

【算法分析】
● 因为浮点数的精度很高，只需要逐渐逼近题目要求的精度就可以了。这里需要注意的是，需要预先设定一个阈值 eps，一般是比题目的精度还要高 2 位，比如题目要求的精度是1e-3，那么就可以设eps=1e-5。如本题中的 while(ri-le>1e-5){……}。
● 当数据比较大时，可能会产生溢出。所以，本题中使用 double mid=le+(ri-le)/2; 而不是 double mid=(le+ri)/2;

【算法代码一】

#include <bits/stdc++.h>
using namespace std;
 
double x,y,c;
bool check(double mid) {
    double rx=sqrt(x*x-mid*mid);
    double ry=sqrt(y*y-mid*mid);
    double h=rx*ry/(rx+ry);
    if(h>c) return true;
    else return false;
}
 
int main() {
    scanf("%lf%lf%lf",&x,&y,&c);
    double le,ri;
    le=0;
    ri=min(x,y);
 
    while(ri-le>1e-5) {
        double mid=(le+ri)/2;
        if(check(mid)) le=mid;
        else ri=mid;
    }
 
    printf("%.3lf\n",le);
 
    return 0;
}
 
/*
in:
30 40 10

out:
26.033
*/

【算法代码二】

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

double x,y,c;
bool check(double mid) {
    double rx=sqrt(x*x-mid*mid);
    double ry=sqrt(y*y-mid*mid);
    double h=rx*ry/(rx+ry);
    if(h<c) return true;
    else return false;
}

int main() {
    scanf("%lf%lf%lf",&x,&y,&c);
    double le,ri;
    le=0;
    ri=min(x,y);

    while(ri-le>1e-5) {
        double mid=(le+ri)/2;
        if(check(mid)) ri=mid;
        else le=mid;
    }

    printf("%.3lf\n",le);

    return 0;
}

/*
in:
30 40 10

out:
26.033
*/

【参考文献】
https://www.acwing.com/solution/content/10674/
https://blog.csdn.net/hnjzsyjyj/article/details/136774256

查看全文

http://www.kler.cn/a/273670.html