HDU3400+三分

把a，d这两个起点和终点之间的中间点三分出来。

其他没什么。

/*  
两次三分  
题意：给定abcd四个点（包括速度，位置），从a到d，求最短时间。  
*/  
#include  
#include  
#include  
#include  
#include  
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 )eps ){  
            mid1 = (L+R)/2.0;  
            mid2 = (mid1+R)/2.0;  
              
            if( solve( mid1 )
#include
#include
#include
#include
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 )eps ){
			mid1 = (L+R)/2.0;
			mid2 = (mid1+R)/2.0;
			
			if( solve( mid1 )