Turn the corner--hdu2438(3分法)

深藏阁楼爱情的钟 2022-08-04 08:53 84阅读 0赞

**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?

![2438-1.jpg][]

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

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

![270026238732409.jpg][]

如图分析，如果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\n");
    29     else
    30     printf("no\n");
    31     }
    32     return 0;
    33 }

[2438-1.jpg]: /images/20220731/259f9cc4b9d8494ab57bcdc86d296555.png
[270026238732409.jpg]: /images/20220731/3b2198569f83435b8428449135eb70d5.png