托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,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?
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
题目链接: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 }