首页 > 代码库 > HDU2438 Turn the corner【三分法】【数学几何】
HDU2438 Turn the corner【三分法】【数学几何】
Turn the corner
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1930 Accepted Submission(s): 736
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
题目大意:有一个直角拐角,给你水平道路宽度Y和竖直高度X,再给你汽车的长l,宽w
问:汽车是否能通过这个拐角。
思路:如果汽车的宽度大于水平道路宽度Y或是竖直高度X,无论如何都通不过。接下来
考虑一般情况。
如图:若汽车最左边与墙一直靠紧,则只需要判断右边最高点是否超过了Y。
设θ为汽车与水平方向的夹角,s为汽车最右边的角到拐点的水平距离。那么
s = l*cos(θ) + w*sin(θ) - x,从而得出 h = s*tan(θ)+w*cos(θ)。
θ角从0~π/2,变化,h则从低到高再到底,且是一个凸形函数。利用三分方法
得到最高点的h,与Y比较判断是否能通过。
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> using namespace std; const double PI = acos(-1.0); double x,y,l,w; double calc(double angle) { double s = l*cos(angle) + w*sin(angle) - x; double h = s*tan(angle) + w*cos(angle); return h; } int main() { while(cin >> x >> y >> l >> w) { double left,right,mid,midmid; left = 0; right = PI/2; while(right-left >= 1e-7) { mid = (left+right)/2; midmid = (mid+right)/2; if(calc(mid) > calc(midmid)) right = midmid; else left = mid; } if(x<w || y<w || calc(mid) > y) cout << "no" << endl; else cout << "yes" << endl; } return 0; }
HDU2438 Turn the corner【三分法】【数学几何】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。