Line belt
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=3400
Mean:
给出两条平行的线段AB, CD,然后一个人在线段AB的A点出发,走向D点,其中,人在线段AB上的速度为P, 在线段CD上的速度为Q,在其他地方的速度为R,求人从A点到D点的最短时间。
analyse:
经典的三分套三分。
首先在AB线段上三分,确定一个点,然后再在CD上三分,确定第二个点,计算出answer。也就是嵌套的三分搜索。
Time complexity: O(logn*logm)
Source code:
// Memory Time // 1347K 0MS // by : crazyacking // 2015-03-31-23.22 #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #define MAXN 1000010 #define LL long long using namespace std; struct point { double x,y; }; point A,B,C,D; double p,q,r; double length(point X,point Y) { return sqrt((X.x-Y.x)*(X.x-Y.x)+(X.y-Y.y)*(X.y-Y.y)); } double time(double a,double b) { point X,Y; X.x=a*(B.x-A.x)+A.x; X.y=a*(B.y-A.y)+A.y; Y.x=b*(C.x-D.x)+D.x; Y.y=b*(C.y-D.y)+D.y; return length(A,X)/p+length(D,Y)/q+length(X,Y)/r; } double ThiDiv(double alen) { double l=0.0,r=1.0,lm,rm; while(r-l>1e-10) { lm=(l*2.0+r)/3; rm=(l+r*2.0)/3; if(time(alen,lm)>=time(alen,rm)) l=lm; else r=rm; } return time(alen,lm)<time(alen,rm)?time(alen,lm):(time(alen,rm)); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); // freopen("C:\\Users\\Devin\\Desktop\\cin.cpp","r",stdin); // freopen("C:\\Users\\Devin\\Desktop\\cout.cpp","w",stdout); int Cas; scanf("%d",&Cas); while(Cas--) { 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=0.0,r=1.0,lm,rm; while(r-l>1e-10) { lm=(l*2.0+r)/3; rm=(l+r*2.0)/3; if(ThiDiv(lm)>=ThiDiv(rm)) l=lm; else r=rm; } printf("%.2f\n",min(ThiDiv(lm),ThiDiv(rm))); } return 0; } /* */