[SCOI 第二试 传送带]二分法 or 二分+暴力 or 直接暴力

【题目】

Description

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的 移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间

Input

输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By
第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy
第三行是3个整数，分别是P，Q，R

Output

输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位

Sample Input

0 0 0 100
100 0 100 100
2 2 1

Sample Output

136.60

Hint

对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
1<=P，Q，R<=10 【算法分析】
好吧，很容易得出路径应该是这样一种形式：
A->p1->p2->D
其中p1在线段AB上，p2在线段CD上。
然后感觉应该是都满足单峰性质的。
表示不会证明。。。只是感觉。
可以用r1 * AB向量和r2 * DC向量分别表示p1、p2。

第一种：
嵌套二分r1和r2。得到速度非常快的一个算法。

第二种：
如果不放心，那么枚举r1，精度卡一下，卡1e-5之类。
然后二分r2。
得到一个比较快的算法。

第三种：
如果还不放心，那么直接暴力它吧。经测试，直接枚举r1和r2，卡精度2e-4，可以在每个测试数据1.8s的情况下暴力AC！
果然，很黄很暴力~

【其他】
我是傻X，因为求的是最小值，而不是最大值。
一开始二分的部分应该l=mid的时候写成r=mid
应该r=mid的时候写成了l=mid。
导致以为不符合单峰性质，所以有了各种暴力尝试。。。

【CODE1】
#include #include #include #include #include using namespace std;
const double eps=1e-6;
int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,Rab,Rcd,R;
double xx1,yy1,xx2,yy2,d1,d2,d3,r1;

inline double dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double Get(double r2){
xx1=(Bx-Ax)*r1+Ax;
yy1=(By-Ay)*r1+Ay;
xx2=(Cx-Dx)*r2+Dx;
yy2=(Cy-Dy)*r2+Dy;
d1=dis(xx1,yy1,Ax,Ay)/Rab;
d2=dis(xx1,yy1,xx2,yy2)/R;
d3=dis(xx2,yy2,Dx,Dy)/Rcd;
return d1+d2+d3;
}

double solve(double tmp){
r1=tmp;
double l=0,r=1,mid;
while (l+eps mid=(l+r)/2;
if (Get(mid) else l=mid;
}
return Get(l);
}

int main(){
cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy>>Rab>>Rcd>>R;
double l=0,r=1,mid;
while (l+eps mid=(l+r)/2;
if (solve(mid) else l=mid;
}
printf("%.2lfn",solve(l));
}
【CODE2】
#include #include #include #include #include using namespace std;
const double eps=1e-5;
int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,Rab,Rcd,R;
double xx1,yy1,xx2,yy2,d1,d2,d3,r1;

inline double dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double Get(double r2){
xx1=(Bx-Ax)*r1+Ax;
yy1=(By-Ay)*r1+Ay;
xx2=(Cx-Dx)*r2+Dx;
yy2=(Cy-Dy)*r2+Dy;
d1=dis(xx1,yy1,Ax,Ay)/Rab;
d2=dis(xx1,yy1,xx2,yy2)/R;
d3=dis(xx2,yy2,Dx,Dy)/Rcd;
return d1+d2+d3;
}

double solve(double tmp){
r1=tmp;
double l=0,r=1,mid;
while (l+eps mid=(l+r)/2;
if (Get(mid) else l=mid;
}
return Get(l);
}

int main(){
cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy>>Rab>>Rcd>>R;
double i=0,ans=1e20;
for (i=0;i<1;i+=eps)
ans=min(ans,solve(i));
printf("%.2lfn",ans);
}
【CODE3】
#include #include #include #include #include using namespace std;
const double eps=1e-6;
const double eps2=1e-7;
const double eeps=2e-4;
int Ax,Ay,Bx,By,Cx,Cy,Dx,Dy,Rab,Rcd,R;

inline double dis(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double Get(double r1,double r2){
double x1,y1,x2,y2,d1,d2,d3;
x1=(Bx-Ax)*r1+Ax;
y1=(By-Ay)*r1+Ay;
x2=(Cx-Dx)*r2+Dx;
y2=(Cy-Dy)*r2+Dy;
d1=dis(x1,y1,Ax,Ay)/Rab;
d2=dis(x1,y1,x2,y2)/R;
d3=dis(x2,y2,Dx,Dy)/Rcd;
return d1+d2+d3;
}

double solve(double r1){
double l,ans=1e20;
for (l=0;l<1;l+=eeps) ans=min(ans,Get(r1,l));
return ans;
}

int main(){
cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy>>Rab>>Rcd>>R;
double l=0,r=1,mid,ans=1e20;
for (l=0;l<1;l+=eeps) ans=min(ans,solve(l));
printf("%.2lfn",ans);
}