HDU 2438 Turn the corner(三分查找)

托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,AC了一题,写法确实方便,还是我太弱了,漫漫AC路!各路大神,以后你们有啥好的简便写法可以在博客下方留个言或私信我,谢谢了!

Turn the corner

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3196    Accepted Submission(s): 1302

Problem Description

Mr. West bought a new car! So he is travelling around the city. One day he comes to a vertical corner. The street he is currently in has a width x, the street he wants to turn to has a width y. The car has a length l and a width d. Can Mr. West go across the corner?

Input

Every line has four real numbers, x, y, l and w. Proceed to the end of file.

Output

If he can go across the corner, print "yes". Print "no" otherwise.

Sample Input

10 6 13.5 4

10 6 14.5 4

Sample Output

yes

no

Source

2008 Asia Harbin Regional Contest Online

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2438

题意:

         给出街道在x轴的宽度X,y轴的宽度Y,还有车的长l和宽w,判断是否能够转弯成功。

题解:

        盗网上大牛一张图,画的很详细

      尽可能让车贴着外面的墙璧转弯,也就是图中的x轴和y轴,此时红线的方程就是图中的方程,此时p点的位置就是让y=X时解得的x值,要保证p点在Y内,也就是-x<y,假若在转弯的所有角度中都满足这个条件,那么就能转弯,分析得,-x先增大后减小,所以用三分求最大-x值。

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 double x,y,l,w;
 4 const double eps=1e-6;
 5 const double pi=acos(-1.0);
 6 double solve(double angle)
 7 {
 8     return (-x+l*sin(angle)+w/cos(angle))/tan(angle);
 9 }
10 int main()
11 {
12     while(scanf("%lf%lf%lf%lf",&x,&y,&l,&w)!=EOF)
13     {
14         double ll=0,rr=pi/2,midx,midy;
15         while(rr-ll>eps)
16         {
17             midx=(ll+ll+rr)/3;
18             midy=(ll+rr+rr)/3;
19             if(solve(midx)>solve(midy))
20             rr=midy;
21             else ll=midx;
22         }
23         if(solve(ll)<y)
24             printf("yes\n");
25         else printf("no\n");
26     }
27     return 0;
28 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏函数式编程语言及工具

SDP(2):ScalikeJDBC-Connection Pool Configuration

  scalikeJDBC可以通过配置文件来设置连接池及全局系统参数。对配置文件的解析是通过TypesafeConfig工具库实现的。默认加载classpath...

3474
来自专栏逍遥剑客的游戏开发

WOW小地图生成

3013
来自专栏算法修养

HDU 1233 还是畅通工程(Kruskal)

还是畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

2635
来自专栏ml

HDUOJ---1233还是畅通工程

还是畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Ja...

3507
来自专栏开发 & 算法杂谈

PAT Advanced 1042

Shuffling is a procedure used to randomize a deck of playing cards. Because sta...

811
来自专栏HansBug's Lab

3891: [Usaco2014 Dec]Piggy Back

3891: [Usaco2014 Dec]Piggy Back Time Limit: 10 Sec  Memory Limit: 128 MB Submit:...

3719
来自专栏jeremy的技术点滴

python开发小技巧

3114
来自专栏GIS讲堂

巧用Arcgis Server的REST接口实现OL2中WMS添加过滤

在实际的应用中,很多时候我们需要对展示的图层进行属性或者空间的过滤,在Geoserver发布的WMS中,可以通过CQL_FILTER来设置过滤条件,但是Arcg...

1233
来自专栏hbbliyong

使用WPF教你一步一步实现连连看(二)

连连看算法 第一步:我们考虑在同行或者同列的情况: 同行或者同列又分三种情况:   第一:边线,RowNum或者ColNum等于0或者9   第二:两...

4019
来自专栏技术之路

WPF MVVM实现TreeView

今天有点时间,做个小例子WPF MVVM 实现TreeView 只是一个思路大家可以自由扩展 文章最后给出了源码下载地址 图1 ?    图2     ? 模...

2669

扫码关注云+社区

领取腾讯云代金券