SCOI2010 传送带

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2010 传送带

Date: Thu Sep 13 06:46:21 CST 2018

In Category: NoCategory

Description：

二维平面上有两条有方向的传送带，起点和终点分别是 $A,B$ 和 $C,D$ ，人在平面上和两条传送带上有三个不同的速度，问从 $A$ 到 $D$ 最少要多少时间。

Solution：

发现在两条传送带上距离都有先增后减的性质，于是三分套三分，先三分第一个传送带的位置，然后再在另一个传送带上三分它的位置即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

double ax,ay,bx,by,cx,cy,dx,dy;

double p,q,w;

double dis(double fx,double fy,double gx,double gy)

{

	return sqrt((fx - gx) * (fx - gx) + (fy - gy) * (fy - gy));

}

double query(double sx,double sy)

{

	double l = 0,r = 1,lef,rig,d;

	double ans = 10000000000000,ans1,ans2;

	double x,y;

	while(r - l > 1e-6)

	{

		d = (r - l) / 3;lef = l + d;rig = r - d;

		x = cx + (dx - cx) * lef;y = cy + (dy - cy) * lef;

		ans1 = dis(x,y,dx,dy) / q + dis(x,y,sx,sy) / w;

		x = cx + (dx - cx) * rig;y = cy + (dy - cy) * rig;

		ans2 = dis(x,y,dx,dy) / q + dis(x,y,sx,sy) / w;

		ans = min(ans,min(ans1,ans2));

		if(ans1 < ans2)r = rig;

		else l = lef;

	}

	return ans;

}

int main()

{

	scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);

	scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);

	scanf("%lf%lf%lf",&p,&q,&w);

	double l = 0,r = 1,lef,rig,d;

	double ans = 10000000000000,ans1,ans2;

	double x,y;

	while(r - l > 1e-6)

	{

		d = (r - l) / 3;lef = l + d;rig = r - d;

		x = ax + (bx - ax) * lef;y = ay + (by - ay) * lef;

		ans1 = query(x,y) + dis(x,y,ax,ay) / p;

		x = ax + (bx - ax) * rig;y = ay + (by - ay) * rig;

		ans2 = query(x,y) + dis(x,y,ax,ay) / p;

		ans = min(ans,min(ans1,ans2));

		if(ans1 < ans2)r = rig;

		else l = lef;

	}

	printf("%.2lf\n",ans);

	return 0;

}

In tag: 算法-三分

wjh15101051