首页 > ACM题库 > HDU-杭电 > hdu 2438 Turn the corner-计算几何-[解题报告]C++
2014
01-26

hdu 2438 Turn the corner-计算几何-[解题报告]C++

Turn the corner

问题描述 :

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?

输入:

Every line has four real numbers, x, y, l and w.
Proceed to the end of file.

输出:

Every line has four real numbers, x, y, l and w.
Proceed to the end of file.

样例输入:

10 6 13.5 4
10 6 14.5 4

样例输出:

yes
no

看了下,感觉这个图画的特别好,一下就明白咯,求出红色线的方程,再使用3分的思想。

首先要对几何平面建系,我的建系方法如图。接着,由于车的转弯是一个动态过程,我们需要研究的是每一个静态的瞬间,看看是否会被“卡住”。







如图,在列出红色的那条直线的方程后,关键要求出其与蓝色线交点P。如果交点在y轴的右方,或者交点P在y轴的左方,且PH<=Y,那么车在这个瞬间就不会被卡住。想象一下,若P在Y轴的左方,那么PH的长度必定是先增后减,表示为函数的话,PH=f(θ)必定是一个凸性函数。因此我们只要求出这个函数在(0,PI/2]这个区间中的极值即可。



在y=xtan(θ)+Lsin(θ)+D/cos(θ)这条式子中,只要把常量X代进y,反解出x,-x就是PH。求出-x的最值,若-x<Y,车就是能够转弯转过去的。

 

#include<iostream>
#include<cmath>
using namespace std;
const double Pi = acos(-1.0), eps = 1e-6;
double x, y, l, w;

double fun(double a)
{
     return -((x - l*sin(a) - w/cos(a))/tan(a));     
}

double find(double l, double r)
{
    double mid, midmid;
    while(r-l > eps)
    {
        mid = (l+r)/2;
        midmid = (r+mid)/2;
        if(fun(mid) > fun(midmid))
           r = midmid;
        else l = mid;                      
    }       
    return l;
}

 
int main()
{ 
    while(cin>>x>>y>>l>>w)
    {
        if(x < w || y < w || fun(find(0, Pi/2)) > y) cout<<"no"<<endl;
        else cout<<"yes"<<endl;                      
                          
    }
    return 0;
}



 

解题转自:http://blog.csdn.net/dnf1990/article/details/8247636


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?