NKOJ 2644 （SCOI 2010） 传送带（三分）

发表于 |
字数统计: 581字 | 阅读时长 ≈ 3min

P2644【SCOI2010 DAY2】传送带

问题描述

　　在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间

输入格式

输入数据第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By
　　第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy
　　第三行是3个整数，分别是P，Q，R

输出格式

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

样例输入

0 0 0 100
100 0 100 100
2 2 1

样例输出

136.60

提示

对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
　　 1<=P，Q，R<=10

此题比较简单，设$F(x,y)$表示在$AB$上走x，在$CD$上走的行走时间，显然是一个单峰函数，三分套三分即可。
需要注意的是不要用直线解析式算交点，直接用线段的长度关系求。

代码：

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
#include<stdio.h>
#include<cmath>
#define ll double 
using namespace std;
ll xa,xb,xc,xd,ya,yb,yc,yd,v1,v2,v3,l1,l2;
ll R(ll a,ll b,ll c,ll d)
{
	return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
ll G(ll x,ll y)
{
	ll x1,y1,x2,y2;
	x1=xa+(xb-xa)*x;
	y1=ya+(yb-ya)*x;
	x2=xd-(xd-xc)*y;
	y2=yd-(yd-yc)*y;
	return l1*x/v1+l2*y/v2+R(x1,y1,x2,y2)/v3;
}
ll F2(ll x)
{
	ll l,r,tl,tr;
	l=0;r=1;
	while(r-l>=0.0000001)
	{
		tl=l+(r-l)/3;
		tr=r-(r-l)/3;
		if(G(x,tl)<G(x,tr))r=tr;
		else l=tl;
	}
	return G(x,tl);
}
ll F1()
{
	ll l,r,tl,tr;
	l=0;r=1;
	while(r-l>=0.0000001)
	{
		tl=l+(r-l)/3;
		tr=r-(r-l)/3;
		if(F2(tl)<F2(tr))r=tr;
		else l=tl;
	}
	return F2(tl);
}
int main()
{
	scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&xa,&ya,&xb,&yb,&xc,&yc,&xd,&yd,&v1,&v2,&v3);
	l1=R(xa,ya,xb,yb);
	l2=R(xc,yc,xd,yd);
	printf("%.2lf",F1());
}