Turn the corner (三分)

Turn the corner

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 151 Accepted Submission(s): 61

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

汽车拐弯问题，给定X, Y, l, d判断是否能够拐弯。

我们发现随着角度θ的增大，最大高度ｈ先增长后减小，即为凸性函数，可以用三分法来求解。

这里的Calc函数需要比较繁琐的推倒公式：
s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
其中s为汽车最右边的点离拐角的水平距离, h为里拐点最高的距离, θ范围从0到90。

3分搜索法

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 const double pi=2*asin(1.0);
 5 double x,y,l,d;
 6 double geth(double an){
 7     double s,h;
 8     s=l*cos(an)-x+d*sin(an);//应该是减x因为车头要对住墙，然后看车尾最高是否大于y 
 9     h=s*tan(an)+d*cos(an);
10     return h;
11 }
12 double ABS(double a){
13     return a>=0?a:-a;
14 }
15 void erfen(){
16     double l=0,m,mm,r=pi/2;
17 //    printf("%lf
",pi);
18     while(ABS(r-l)>1e-10){
19         m=(l+r)/2;
20         mm=(m+r)/2;
21         if(geth(m)>=geth(mm))r=mm;
22         else l=m;
23     }
24 //    printf("%lf
",geth(m));
25     if(geth(l)>y)puts("no");
26     else puts("yes");
27 }
28 int main(){
29     while(~scanf("%lf%lf%lf%lf",&x,&y,&l,&d)){
30         erfen();
31     }
32     return 0;
33 }