hdu 2438 Turn the corner（几何+三分）

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

 

摘自大牛的解题报告:

题意：给定一个直角弯道的两条道路的宽度，然后再给出汽车的长度与宽度，问汽车能否通过该弯道？

 

如下图：

 

要使汽车能转过此弯道，那么就是汽车的左边尽量贴着那个直角点，而汽车的右下后方的点尽量贴着最下面的边。

我们以O点为原点建立直角坐标系，我们可以根据角a给出P点横坐标的函数F(a)

 

那么很容易得到：

 

其中有条件：，可以很容易证明是一个单峰函数，所以接下来就是三分了，如果的最大值小于等于

 

y，那么就能通过此直角弯道，否则就通不过。

 

在三分的时候，写成这样

mid1=(low+high)/2;
mid2=(mid1+high)/2;

一直WA，直到写成下面这样才AC，

double mid1=(2*low+high)/3; 
double mid2=(low+2*high)/3;

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
#include <stack>
using namespace std;
int dirx[]={0,0,-1,1};
int diry[]={-1,1,0,0};
#define PI acos(-1.0)
#define max(a,b) (a) > (b) ? (a) : (b)  
#define min(a,b) (a) < (b) ? (a) : (b)
#define ll long long
#define eps 1e-10
#define MOD 1000000007
#define N 1000000
#define inf 1<<26

double x,y,l,w;
double equ(double t)  
{  
    return l*cos(t)+(w-x*cos(t))/sin(t);  
}  
int main()
{
    
    while(scanf("%lf%lf%lf%lf",&x,&y,&l,&w)==4){
        double low=0;
        double high=PI/2.0;
    //    double mid1=(low+high)/2;
        //double mid2;
        double sum1;
        double sum2;
        while(high-low>eps){
            double mid1=(2*low+high)/3;//要这样找mid 
            double mid2=(low+2*high)/3;//要这样找mid 
            sum1=equ(mid1);
            sum2=equ(mid2);
            if(sum1<sum2){
                low=mid1;
            }
            else{
                high=mid2;
            }
            
        }
        if(equ(low)<=y){
            printf("yes
");
        }
        else{
            printf("no
");
        }
        
    }
    return 0;
}