hdu Turn the corner

简介:

Turn the corner

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 151 Accepted Submission(s): 61
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


汽车拐弯问题,给定X, Y, l, d判断是否能够拐弯。首先当X或者Y小于d,那么一定不能。
其次我们发现随着角度θ的增大,最大高度h先增长后减小,即为凸性函数,可以用三分法来求解。

这里的Calc函数需要比较繁琐的推倒公式:
s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
其中s为汽车最右边的点离拐角的水平距离, h为里拐点最高的距离, θ范围从0到90。

3分搜索法

复制代码
#include <iostream>
#include
<stdio.h>
#include
<math.h>
using namespace std;
double pi = acos(-1.0);
double x,y,l,w,s,h;
double cal(double a)
{
s
= l*cos(a)+w*sin(a)-x;
h
= s*tan(a)+w*cos(a);
return h;
}
int main()
{
double left,right,mid,midmid;
while(scanf("%lf%lf%lf%lf",&x,&y,&l,&w)!=EOF)
{
left
= 0.0;
right
= pi/2;
while(fabs(right-left)>1e-8)
{
mid
= (left+right)/2;
midmid
= (mid+right)/2;
if(cal(mid)>=cal(midmid))right = midmid;
else left = mid;
}
if(cal(mid)<=y)printf("yes\n");
else printf("no\n");
}
return 0;
}
复制代码
本文转自NewPanderKing51CTO博客,原文链接: http://www.cnblogs.com/newpanderking/archive/2011/08/25/2153773.html  ,如需转载请自行联系原作者
相关文章
|
6月前
Knight Moves(POJ2243)
Knight Moves(POJ2243)
|
图形学
hdu1086 You can Solve a Geometry Problem too(判断线段相交)
hdu1086 You can Solve a Geometry Problem too(判断线段相交)
71 0
UVA699 下落的树叶 The Falling Leaves
UVA699 下落的树叶 The Falling Leaves
UVA699 下落的树叶 The Falling Leaves
AtCoder Beginner Contest 176 D - Wizard in Maze(01BFS)
AtCoder Beginner Contest 176 D - Wizard in Maze(01BFS)
115 0
HDOJ/HDU 1372 Knight Moves(经典BFS)
HDOJ/HDU 1372 Knight Moves(经典BFS)
135 0