Turn the corner--hdu2438(3分法)

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

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

分析：这个题就是看车子是否能通过这个转角！

如图分析，如果h最大的时候还是小于y的，那么车一定能通过！

即变相的求函数h=l*sin(a)-x*tan(a)+d/cos(a)的最大值，显然用三分法！

 1 #include<stdio.h>
 2 #include<math.h>
 3 #define PI 3.1415926535
 4 double l,d,x,y;
 5 double hs(double p)
 6 {
 7     double w;
 8     w=l*sin(p)-x*tan(p)+d/cos(p);//函数，计算h
 9     return w;
10 }
11 int main()
12 {
13     while(scanf("%lf%lf%lf%lf",&x,&y,&l,&d)!=EOF)
14     {
15     double a=0,b=PI/2,mid,midmid;
16     do
17     {
18         //mid=(b-a)/3+a;
19         //midmid=(b-a)*2/3+a;
20         mid=(a+b)/2;
21         midmid=(mid+b)/2;
22         if(hs(mid)>hs(midmid))
23         b=midmid;
24         else
25         a=mid;
26     }while(b-a>1e-10);
27     if(hs(mid)<y)
28     printf("yes
");
29     else
30     printf("no
");
31     }
32     return 0;
33 }