【SCOI2010】【JZOJ 4692】 传送带

Description

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。FTD在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在FTD想从A点走到D点，他想知道最少需要走多长时间 对于100%的数据 1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000 1<=P,Q,R<=10 输出保留两位小数

Analysis

首先，我没什么头绪，想到将线段拆成很多个点，跑最短路。 后来发现根本不需要这样。 首先还是枚举线段AB上的一个出发点P，从A走到P 然后从P走到CD上一点Q，再从Q走到D。 可以发现CD上有一个最优点满足代价最小，因此可以三分CD上的点。 这样就能过了，但是时间太慢了。 再发现，线段AB上的那个点也是可以三分的。 于是变成了喜闻乐见的三分套三分。快得飛飛飛上天。

Code

#include<cstdio> #include<cmath> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef double db; const db N=500000,eps=1e-5; db P,Q,R,k,bb; struct point { db x,y; }a,b,c,d; db sqr(db x){return x*x;} db dis(point a,point b) { return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); } db calc(point p,point p1) { return dis(a,p)/P+dis(p,p1)/R+dis(p1,d)/Q; } db get(point p) { point l=c,r=d,p1,p2; while(abs(l.x-r.x)>1e-5 || abs(l.y-r.y)>1e-5) { p1.x=(l.x+r.x)/2,p1.y=(l.y+r.y)/2; p2.x=(p1.x+r.x)/2,p2.y=(p1.y+r.y)/2; if(calc(p,p1)<calc(p,p2)) r=p2; else l=p1; } return calc(p,l); } int main() { scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y,&P,&Q,&R); db ans=N; point l=a,r=b,p1,p2; while(abs(l.x-r.x)>1e-5 || abs(l.y-r.y)>1e-5) { p1.x=(l.x+r.x)/2,p1.y=(l.y+r.y)/2; p2.x=(p1.x+r.x)/2,p2.y=(p1.y+r.y)/2; if(get(p1)<get(p2)) r=p2; else l=p1; } printf("%.02lf",get(l)); return 0; }