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; }