传送带 方法记录

原题链接

[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%) 的数据，(1le A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_yle10^3)，(1le P,Q,Rle10)。

题解

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

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

解题的关键在于分析路线

在线段(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("%.2lfn",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("%.2lfn",get_ant(l)); 	return 0; } 

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