hdu3400（三分套三分）-白红宇

hdu3400（三分套三分）

阅读量：5153 次

发布时间：2019-06-13

本文共 1834 字，大约阅读时间需要 6 分钟。

题意：平面上两条线段 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;}