Turn the corner
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 41 Accepted Submission(s) : 9
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
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.
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
思路：
1. 当x或y小于d时，一定不能够拐弯。
2. 当x和y都大于d时，
其中：
s
= l * cos(θ) + w * sin(θ) - x;
= l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
这是关于θ的一个凸函数，我们要求其在 [0, π/2] 之间的最大值，故可以用三分法。
算法：
三分法
类似二分的定义Left和Right
mid = (Left + Right) / 2
midmid = (mid + Right) / 2;
如果mid靠近极值点，则Right = midmid；
否则(即midmid靠近极值点)，则Left = mid;
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
double PI=acos(-1.0);
double x,y,l,d;
double f(double tha)
{
double s,h;
s=l*cos(tha)+d*sin(tha)-x;
h=s*tan(tha)+d*cos(tha);
return h;
}
int main ()
{
double h,left,right,mid,midmid;
while (cin>>x>>y>>l>>d)
{
if (x<=d || y<=d)
{
cout<<"no"<<endl;
continue;
}
else
{
left=0.0;
right=PI/2;
while(fabs(right-left)>1.0e-8)
{
mid=(left+right)/2;
midmid=(mid+right)/2;
if (f(mid)>f(midmid))
right=midmid;
else
left=mid;
}
}
if ((f(mid))<=y)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return 0;
}