HDU3400+三分

把a，d這兩個起點和終點之間的中間點三分出來。

其他沒什麼。

/*  
兩次三分  
題意：給定abcd四個點（包括速度，位置），從a到d，求最短時間。  
*/  
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<math.h>  
#include<algorithm>  
using namespace std;  
const int maxn = 105;  
const double eps = 1e-8;  
const double pi = acos(-1.0);  
struct Point {  
    double x,y;  
};  
Point a,b,c,d;  
double P,Q,R,ans1,ans2;  
  
double dis( Point aa,Point bb ){  
    return sqrt( (aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y) );  
}  
  
double GetAns( double tt1,double tt2 ){  
    double ans;  
    Point temp1,temp2;  
    temp1.x = a.x+tt1*(b.x-a.x),temp1.y = a.y+tt1*(b.y-a.y);  
    temp2.x = c.x+tt2*(d.x-c.x),temp2.y = c.y+tt2*(d.y-c.y);  
    ans = dis( a,temp1 )/P+dis( temp1,temp2 )/R+dis( temp2,d )/Q;  
    return ans;  
}  
  
double solve( double x ){  
    double L,R,mid1,mid2;  
    L = 0;  
    R = 1;  
    while( R-L>eps ){  
        mid1 = (L+R)/2.0;  
        mid2 = (mid1+R)/2.0;  
          
        if( GetAns( x,mid1 )<GetAns( x,mid2 ) ){  
            ans2 = mid1;  
            R = mid2;  
        }  
        else{  
            ans2 = mid2;  
            L = mid1;  
        }  
    }  
    return GetAns( x,ans2 );  
}  
  
int main(){  
    int T;  
    scanf("%d",&T);  
    while( T-- ){  
        scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);  
        scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);  
        scanf("%lf%lf%lf",&P,&Q,&R);  
        double L,R,mid1,mid2;  
        L = 0;  
        R = 1;  
        while( R-L>eps ){  
            mid1 = (L+R)/2.0;  
            mid2 = (mid1+R)/2.0;  
              
            if( solve( mid1 )<solve( mid2 ) ){  
                ans1 = mid1;  
                R = mid2;  
            }  
            else{  
                ans1 = mid2;  
                L = mid1;  
            }  
        }  
        printf("%.2lf\n",GetAns( ans1,ans2 ));  
    }  
    return 0;  
}  

/*
兩次三分
題意：給定abcd四個點（包括速度，位置），從a到d，求最短時間。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn = 105;
const double eps = 1e-8;
const double pi = acos(-1.0);
struct Point {
	double x,y;
};
Point a,b,c,d;
double P,Q,R,ans1,ans2;

double dis( Point aa,Point bb ){
	return sqrt( (aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y) );
}

double GetAns( double tt1,double tt2 ){
	double ans;
	Point temp1,temp2;
	temp1.x = a.x+tt1*(b.x-a.x),temp1.y = a.y+tt1*(b.y-a.y);
	temp2.x = c.x+tt2*(d.x-c.x),temp2.y = c.y+tt2*(d.y-c.y);
	ans = dis( a,temp1 )/P+dis( temp1,temp2 )/R+dis( temp2,d )/Q;
	return ans;
}

double solve( double x ){
	double L,R,mid1,mid2;
	L = 0;
	R = 1;
	while( R-L>eps ){
		mid1 = (L+R)/2.0;
		mid2 = (mid1+R)/2.0;
		
		if( GetAns( x,mid1 )<GetAns( x,mid2 ) ){
			ans2 = mid1;
			R = mid2;
		}
		else{
			ans2 = mid2;
			L = mid1;
		}
	}
	return GetAns( x,ans2 );
}

int main(){
	int T;
	scanf("%d",&T);
	while( T-- ){
		scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
		scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
		scanf("%lf%lf%lf",&P,&Q,&R);
		double L,R,mid1,mid2;
		L = 0;
		R = 1;
		while( R-L>eps ){
			mid1 = (L+R)/2.0;
			mid2 = (mid1+R)/2.0;
			
			if( solve( mid1 )<solve( mid2 ) ){
				ans1 = mid1;
				R = mid2;
			}
			else{
				ans1 = mid2;
				L = mid1;
			}
		}
		printf("%.2lf\n",GetAns( ans1,ans2 ));
	}
	return 0;
}