【Uva10566】Crossed Ladders

Love The Way You Lie 2022-09-24 06:21 124阅读 0赞

这里写图片描述
这里写图片描述

列出一个包含x,y,c的关系式，设宽为w，底边垂线左边为a，根据相似三角形关系：
1.a/w=c/sqrt(y*y-w*w);
2.(w-a)/w=c/sqrt(y*y-w*w);
两式合并消去a得：
c/sqrt(x*x-w*w)+c/sqrt(y*y-w*w)=1;
能推出c与w有同增同减关系，所以当带入mid小于1时，实际w大于mid；反之小于mid，以此二分，再注意精度即可（误差小于1e-6）。

  1. #include<stdio.h>
  2. #include<math.h>
  3. double x,y,c;
  4. bool judge(double mid) {
  5.     return c/sqrt(x*x-mid*mid)+c/sqrt(y*y-mid*mid)<1;
  6. }
  7. int main() {
  8.     int T,id=0;
  9.     scanf("%d",&T);
  10.     while(T--) {
  11.         scanf("%lf%lf%lf",&x,&y,&c);
  12.         double t;
  13.         t=x<y?x:y;
  14.         double l=0,r=t;
  15.         double mid;
  16.         while(fabs(r-l)>5*1e-7) {
  17.             mid=(l+r)/2;
  18.             if(judge(mid))
  19.                 l=mid;
  20.             else
  21.                 r=mid;
  22.         }
  23.         printf("Case %d: %.7lf\n",++id,mid);
  24.     }
  25.     return 0;
  26. }

http://acm.hust.edu.cn/vjudge/contest/123973#problem/E

发表评论

表情：
评论列表 （有 0 条评论，124人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Word Ladder--LeetCode

    这道题看似一个关于字符串操作的题目，其实要解决这个问题得用图的方法。我们先给题目进行图的映射，顶点则是每个字符串，然后两个字符串如果相差一个字符则我们进行连边。接下来看看这个方

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 265 阅读