程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu3400（三分套三分）

hdu3400（三分套三分）

編輯：C++入門知識

題意：平面上兩條線段 AB，CD。 A到B的速度v1，C到D的速度v2，其他地方的速度V3。求A到D的最短時間。

解法：三分嵌套三分，首先如果ＡＢ上的點確定後，確定ＣＤ的點的確定應該是符合三分性質的，應該是單調或最多凸型分布的。那麼確定ＡＢ上的點，也應該不會出現多個峰谷吧。沒有嚴格證明，是知道有個這個三分嵌套三分的題目才來做的。

代碼：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps (1e-8)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=10100;
const int INF=1000000007;

struct point
{
    double x,y;
} points[4];
double s1,s2,s3;
double gettime(const point& a,const point& b,double speed)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))/speed;
}
double getlen(double rat1,double rat2)
{
    double ans=0;
    point p1;
    p1.x=points[0].x+(points[1].x-points[0].x)*rat1;
    p1.y=points[0].y+(points[1].y-points[0].y)*rat1;

    point p2;
    p2.x=points[3].x+(points[2].x-points[3].x)*rat2;
    p2.y=points[3].y+(points[2].y-points[3].y)*rat2;
    ans=gettime(points[0],p1,s1)+gettime(p1,p2,s2)+gettime(p2,points[3],s3);
    return ans;
}
double solve(double m)
{
    double l=0,r=1.0;
    while(r-l>eps)
    {
        double mid=(r+l)/2.0;
        double midr=(mid+r)/2.0;
        if(getlen(m,mid)>getlen(m,midr))
            l=mid;
        else
            r=midr;
    }
    return getlen(m,l);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        for(int i=0; i<4; i++)
            scanf("%lf%lf",&points[i].x,&points[i].y);
        scanf("%lf%lf%lf",&s1,&s3,&s2);
        double l=0,r=1;
        while(r-l>eps)
        {
            double mid=(l+r)/2.0;
            double midr=(mid+r)/2.0;
            if(solve(mid)>solve(midr))
                l=mid;
            else
                r=midr;
        }
        printf("%.2f\n",solve(r));
    }
    return 0;
}