原题链接
[SCOI2010]传送带
题目描述
\(2\ 维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段 \(\text{AB}\ 和线段 \(\text{CD}\。lxhgww 在 \(\text{AB}\ 上的移动速度为 \(P\，在 \(\text{CD}\ 上的移动速度为 \(Q\，在平面上的移动速度 \(R\。现在 lxhgww 想从 \(\text A\ 点走到 \(\text D\ 点，他想知道最少需要走多长时间。
输入格式
\(4\ 个整数，表示 \(\text A\ 和 \(\text B\ 的坐标，分别为 \(A_x\，\(A_y\，\(B_x\，\(B_y\。
\(4\ 个整数，表示 \(\text C\ 和 \(\text D\ 的坐标，分别为 \(C_x\，\(C_y\，\(D_x\，\(D_y\。
\(3\ 个整数，分别是 \(P\，\(Q\，\(R\。
输出格式
\(\text A\ 点走到 \(\text D\ 点的最短时间，保留到小数点后 \(2\ 位。
样例 #1
样例输入 #1
0 0 0 100
100 0 100 100
2 2 1样例输出 #1
136.60提示
对于 \(100\%\ 的数据，\(1\le A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\le10^3\，\(1\le P,Q,R\le10\。
题解
考试的时候，我第一反应是胡不归问题，但数据不允许用胡不归的任何结论。然后思考的方向就转表成了计算几何，最终打了个伪的三分。
解题的关键在于分析路线
\(AB\上取一点\(P1\,在线段\(CD\上取一点\(P2\,那么运动路线就是\(A\->\(P1\->\(P2\->\(D\。
枚举法
\(P1\,\(P2\在各自线段上的位置，即枚举两个转折点。
分的份数越多，精度越高，用的时间也越长），然后二维枚举每一对等分点，计算出在这两个点转折，总路程花费的时间，并统计出最小的时间。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double eps=0.00025;
double ax,ay,bx,by,cx,cy,dx,dy;
double p,q,r;
double ans=1e9;
double get_tim(double x1,double y1,double x2,double y2
{
double s1=sqrt((x1-ax*(x1-ax+(y1-ay*(y1-ay;
double s2=sqrt((x1-x2*(x1-x2+(y1-y2*(y1-y2;
double s3=sqrt((dx-x2*(dx-x2+(dy-y2*(dy-y2;
double res=s1*1.0/p+s2*1.0/r+s3*1.0/q;
return res;
}
int main(
{
freopen("tran.in","r",stdin;
freopen("tran.out","w",stdout;
scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by;
scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy;
scanf("%lf%lf%lf",&p,&q,&r;
for(double mul1=0;mul1<=1;mul1+=eps
{
for(double mul2=0;mul2<=1;mul2+=eps
{
double x1=ax+(bx-ax*1.0*mul1;
double y1=ay+(by-ay*1.0*mul1;
double x2=cx+(dx-cx*1.0*mul2;
double y2=cy+(dy-cy*1.0*mul2;
ans=min(ans,get_tim(x1,y1,x2,y2;
}
}
printf("%.2lf\n",ans;
return 0;
}当然，本题还有另外一种做法：三分法
三分法
\(A\->\(P1\->\(P2\->\(D\.”进行思考。
我们将从起点开始，在线段上行走的这段距离设为 \(x\ ,运动的总时间设为 \(tim\ 。
\(PART 1\
平面速度大于线段速度。
\(x\ 与 \(tim\ 的函数图像就是单调函数（实质上是单峰函数的一半）。
\(PART 2\
接下来再考虑，平面速度小于线段速度。
而\(x\ 与 \(tim\ 的函数图像就是单峰函数。
接下来就可以使用三分法了。
三分套三分的样式。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-12;
double ax,ay,bx,by,cx,cy,dx,dy;
double p,q,r;
double ans=1e9;
double get_tim(double k1,double k2//选出两个情况，计算时间
{
double x1=(bx-ax*k1+ax;
double y1=(by-ay*k1+ay;
double x2=(dx-cx*k2+cx;
double y2=(dy-cy*k2+cy;
double s1=sqrt((x1-ax*(x1-ax+(y1-ay*(y1-ay;
double s2=sqrt((x1-x2*(x1-x2+(y1-y2*(y1-y2;
double s3=sqrt((dx-x2*(dx-x2+(dy-y2*(dy-y2;
double res=s1*1.0/p+s2*1.0/r+s3*1.0/q;
return res;
}
double get_ant(double k//选定一条边上的情况后选择另一条边上的情况
{
double l=0,r=1;
while(r-l>=eps
{
double ml=l+(r-l/3.0;
double mr=r-(r-l/3.0;
if(get_tim(k,ml<get_tim(k,mr r=mr;
else l=ml;
}
return get_tim(k,l;
}
int main(
{
freopen("tran.in","r",stdin;
freopen("tran.out","w",stdout;
scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by;
scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy;
scanf("%lf%lf%lf",&p,&q,&r;
double l=0,r=1;
while(r-l>=eps
{
double ml=l+(r-l/3.0;
double mr=r-(r-l/3.0;
if(get_ant(ml<get_ant(mr r=mr;
else l=ml;
}
printf("%.2lf\n",get_ant(l;
return 0;
}使用三分法可以减少枚举次数，使得用时明显减少，在对上更大的数据时，三分法的优势也会更加显著。