传送带 方法记录

原题链接

[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$。

输出格式

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

样例 #1

样例输入 #1

0 0 0 100
100 0 100 100
2 2 1

样例输出 #1

136.60

提示

对于 $100\mathrm{\%}$ 的数据，$1\le A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\le {10}^3$，$1\le P,Q,R\le 10$。

题解

涉及到精度的问题确实还没什么经验啊。

考试的时候，我第一反应是胡不归问题，但数据不允许用胡不归的任何结论。然后思考的方向就转表成了计算几何，最终打了个伪的三分。

解题的关键在于分析路线

在线段$AB$上取一点$P1$,在线段$CD$上取一点$P2$,那么运动路线就是$A$->$P1$->$P2$->$D$.

枚举法

由于题目对精度的要求比较小（只保留两位小数），所以接下来的策略就是枚举$P1$,$P2$在各自线段上的位置，即枚举两个转折点。

具体地，我们将两条线段分为若干等份（分的份数越多，精度越高，用的时间也越长），然后二维枚举每一对等分点，计算出在这两个点转折，总路程花费的时间，并统计出最小的时间。

#include
#include
#include
#include
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$ .

$PART1$

先考虑比较***钻的情况，平面速度大于线段速度。

这种情况下，只走平面无疑是最明智的。因为走线段又慢又绕路，吃力不讨好。$x$ 与 $tim$ 的函数图像就是单调函数（实质上是单峰函数的一半）。

但这种情况仍然可以使用三分法，因为最终决策点会被逐渐推向起点处，所以三分法在对上这种情况时仍有正确性。（这也是为什么说看似单调函数的图像实质上是单峰函数的一半）

$PART2$

接下来再考虑，平面速度小于线段速度。

这时候我们就可以选择性地走线段了。由于三角形的性质，刚开始的时候走线段会产生正收益，但当前位置与终点连线的斜率逐渐减小，正收益会逐渐降低，最终变为负收益。而这个由正收益转变为负收益的拐点，就是使全程用时最小的转折点。

而$x$ 与 $tim$ 的函数图像就是单峰函数。

接下来就可以使用三分法了。

由于我们需要做出两个决策，分别是两条线段上的转折点，所以我们考虑先用三分法选定一条线段上的某个转折点，再用三分法选择另一条线段上的某个转折点。这将会是一个三分套三分的样式。

方便起见，我们三分的对象是部分占总体的比例。

#include
#include
#include
#include
#include
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;
}

使用三分法可以减少枚举次数，使得用时明显减少，在对上更大的数据时，三分法的优势也会更加显著。