[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);
}

加入对话

2条评论

留下评论

您的电子邮箱地址不会被公开。