传送带 方法记录

时间:2022-11-07 21:05:51

原题链接

题目描述

在一个 \(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\%\) 的数据,\(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;
}

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