hdu 2438 Turn the corner [ 三分 ]

传送门

Turn the corner

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

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

 

Recommend

gaojie   |   We have carefully selected several similar problems for you:  2444 2441 2442 2443 2440

 

 

题解转一发：

http://www.cnblogs.com/wally/archive/2013/05/14/3077383.html

 

网上大牛思路：

可以根据边界，汽车已经转弯，设水平方向为x轴，垂直方向为y轴。

则汽车的内边界(靠近里面的边界)的直线方程式f(x)为：y=x*tan(a)+l*sin(a)+d/cos(a).其中a是汽车与x轴的夹角

当y=X时，求解出的-x即为汽车的内边界到y轴的距离h，若h小于Y即可转弯，若大于Y就不能转弯。
所以只需要利用方程式，求-x的最大值，即可判断能否通过。
由于f(x)是凸函数(随着x的增大y先增大后减小)，所以，需要借助三分求解。

图示：

第一道三分求极值题啊！！！

Run ID	Submit Time	Judge Status	Pro.ID	Exe.Time	Exe.Memory	Code Len.	Language	Author
13216500	2015-03-23 09:01:02	Accepted	2438	0MS	1688K	946 B	G++	czy

#include <cstdio>
#include <cmath>

using namespace std;

const double mi = 1e-7;
const double eps = 1e-9;
const double pi = 4.0 * atan(1.0);

double x,y,l,d;

double cal(double a)
{
    return (-x + l * sin(a) + d / cos(a)) / tan(a) ;
}

int main()
{
    while(scanf("%lf%lf%lf%lf",&x,&y,&l,&d)!=EOF)
    {
        if(d>y || d>x){
            printf("no
");continue;
        }
        double low=0,high = pi / 2,mid,mmid;
        double te1,te2;
        while(high - low > mi)
        {
            mid = (low + high) / 2;
            mmid = (low + mid) / 2;
            te1 = cal(mid);
            te2 = cal(mmid);
            if(te1 > te2){
                low = mmid;
            }
            else{
                high = mid;
            }
        }
        te1 = cal(low);
        if(te1 < y){
            printf("yes
");
        }
        else{
            printf("no
");
        }
    }
}