刷题记录:牛客NC20276[SCOI2010]传送带

传送门:牛客

题目描述:

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在
AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少
需要走多长时间
输入:
0 0 0 100
100 0 100 100
2 2 1
输出:
136.60
1
2
3
4
5
6
7
8
9

当年四川的一道省选题,难度还是挺大的,牛客四星,洛谷蓝题

感觉这种题目有一种求平面上最短点对的意味,但是其实并不是,因为在此题中在不同的地方的速度是不一样的,所以我们得想想其他方法.

方法一:巧妙的暴力

1. 对于这种有精度要求的题目,显然我们首先想到的肯定是暴力,但是该如何暴力的去解决这种问题呢,这道题的暴力解法感觉与这道题,有一种异曲同工之处,可以先去我的这篇博客中看看这种解法,再来观看此法(注意那道题我的解法也不是正解,正解和此题一样是三分,但是那道题我并不想去做正解,不要问我为什么QAQ).

这种解法就是直接枚举两个线段的每一个点,但是因为是浮点数,显然我们是没办法枚举完的(小数是无限的),但是因为是有精度的,所以我们可以取巧的根据精度来设置我们每次走的步数即可(在这道题我直接分成5200组),其他具体的注意点也就是两点间的距离等等的一些小问题,都很好解决

具体代码:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
double P,Q,R;
int fenlie=5200;
double dist(double x1,double y1,double x2,double y2) {
	return sqrt((y1-y2)*(y1-y2)+(x1-x2)*(x1-x2));
}
int main() {
	cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy;
	cin>>P>>Q>>R;
	for(int i=0;i<=5200;i++) {
		double F_x=(Bx-Ax)/5200*i+Ax;
		double F_y=(By-Ay)/5200*i+Ay;
		for(int j=0;j<=5200;j++) {
			double S_x=(Dx-Cx)/5200*j+Cx;
			double S_y=(Dy-Cy)/5200*j+Cy;
			double kk=dist(Ax,Ay,F_x,F_y)/P+dist(F_x,F_y,S_x,S_y)/R+dist(S_x,S_y,Dx,Dy)/Q;
			ans=min(ans,kk);
		}
	}
	printf("%.2lf\n",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

显然如果是考场中碰到这种题目的话我会选择打个暴力直接了事(并且这个暴力竟然能直接过),但是平时我们是需要做做正解的

正解:三分

首先我们知道三分的前提肯定是需要一个单峰函数的,那么作为这道题,我们的三分思路是先三分AB线段上的一个点E(E是AB上的转折点,F是CD上的)(此时我们假设我们的dist(E,F)是关于E的一个单峰函数,在后面会给予证明),对于每一个三分出来的E点,我们都继续基于这个E点开始对CD线段进行三分(此时我们假设dist(E,F)+dist(F,D)是关于F的一个单峰函数(其实dist(F,D)是一个一次函数,后面会证明)),然后根据返回的E,F点求出距离和进行指针移动

下面是繁杂的证明部分,没有打Latex,可能不易观看…

下面先证明dist(A,E)是关于E的一个单峰函数

显然我们根据两点间的距离公式有dist(E,F)=sqrt((Ye-Yf)^2-(Xe-Xf)^2)

又因为我们的Yf=aX+b(线段为一次函数)

所以我们可以得到一个根号里的二次函数形式,显然这个函数是一个单峰函数(根号单调,二次函数单峰)

我们再来证明dist(F,D)是一个一次函数,设m=FC/CD,此时Yf=Xc+m*(Xd-Xc)

dist(F,D)=sqrt(1+k^2)*sqrt(Xf-Xd)
=sqrt(1+k^2)*sqrt((1-m)*(Xc-Xd))

此时我们的k,Xc,Xd显然都是已知的,我们此时得到的函数可以近似的看做关于m的一个类一次函数

并且我们知道当一个二次函数加上一个一次函数时显然还是一个单峰函数

证毕
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

证明是单峰函数之后我们就可以轻易的写出我们的三分代码啦,关于三分模板的讲解也已上线我的博客QAQ

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
double Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
double P,Q,R;
int fenlie=5200;
double dist(double x1,double y1,double x2,double y2) {
	return sqrt((y1-y2)*(y1-y2)+(x1-x2)*(x1-x2));
}
double calc(double Ex,double Ey) {
	double lx=Cx,ly=Cy,rx=Dx,ry=Dy;
	while(dist(lx,ly,rx,ry)>eps) {
		double tempx=(rx-lx)/3,tempy=(ry-ly)/3;
		double lmidx=lx+tempx,lmidy=ly+tempy,rmidx=rx-tempx,rmidy=ry-tempy;
		double ans1=dist(Ex,Ey,lmidx,lmidy)/R+dist(lmidx,lmidy,Dx,Dy)/Q;
		//计算EF+FD的最小值
		double ans2=dist(Ex,Ey,rmidx,rmidy)/R+dist(rmidx,rmidy,Dx,Dy)/Q;
		if(ans2-ans1>eps) rx=rmidx,ry=rmidy;
		else lx=lmidx,ly=lmidy;
	}
	return dist(Ex,Ey,lx,ly)/R+dist(lx,ly,Dx,Dy)/Q;
}
int main() {
	cin>>Ax>>Ay>>Bx>>By>>Cx>>Cy>>Dx>>Dy;
	cin>>P>>Q>>R;
	double lx=Ax,ly=Ay,rx=Bx,ry=By;//三分AB线段
	while(dist(lx,ly,rx,ry)>eps) {
		double tempx=(rx-lx)/3,tempy=(ry-ly)/3;
		double lmidx=lx+tempx,lmidy=ly+tempy,rmidx=rx-tempx,rmidy=ry-tempy;
		double ans1=calc(lmidx,lmidy)+dist(Ax,Ay,lmidx,lmidy)/P;
		double ans2=calc(rmidx,rmidy)+dist(Ax,Ay,rmidx,rmidy)/P;
		//记录A到E点的距离,,calc用来枚举此时此刻CD上的最优点F		
		if(ans2-ans1>eps) rx=rmidx,ry=rmidy;
		else lx=lmidx,ly=lmidy;
	}
	printf("%.2lf\n",calc(lx,ly)+dist(Ax,Ay,lx,ly)/P);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59