Turn the corner
TimeLimit: 1 Second MemoryLimit: 32 Megabyte
Totalsubmit: 637 Accepted: 175
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
heru 5081 Turn the corner 08年哈尔滨regional网络赛
http://acm.hrbeu.edu.cn/index.php?act=problem&id=1280
出处：http://hi.baidu.com/vfxupdpaipbcpuq/item/81b21d1910ea729c99ce33db
汽车拐弯问题，给定X, Y, l, d判断是否能够拐弯。首先当X或者Y小于d，那么一定不能。
其次我们发现随着角度θ的增大，最大高度ｈ先增长后减小，即为凸性函数，可以用三分法来求解。
这里的Calc函数需要比较繁琐的推倒公式：
s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
其中s为汽车最右边的点离拐角的水平距离, h为里拐点最高的距离, θ范围从0到90。
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<memory.h>
#include<math.h>
#define eps 1e-15
#define PI 3.1415926535897932384626
using namespace std;
double x,y,l,w;
int sgn(double a)
{
return (a>eps)-(a<-eps);
}
double dist(double a)
{
double s=l*cos(a)+w*sin(a)-x;
double h=s*tan(a)+w*cos(a);
return h;
}
double work()
{
double mid,midmid;
double l,r;l=0;r=PI*0.5;
while(sgn(r-l)>0)
{
mid=(l+r)*0.5;
midmid=(mid+r)*0.5;
if(dist(mid)>=dist(midmid))
r=midmid;
else
l=mid;
}
return dist(r);
}
int main()
{
double ff;
while(scanf("%lf%lf%lf%lf",&x,&y,&l,&w))
{
if(w>x||w>y)
printf("yes\n");
else
{
ff=work();
if(sgn(y-ff)>0)
printf("yes\n");
else
printf("no\n");
}
}
return 0;
}