LuoguP2571「SCOI2010」题解

发表于 更新于

三分套三分

Description

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

Samples

Input #1

1
2
3
0 0 0 100
100 0 100 100
2 2 1

Output #1

1
136.60

Hint

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

Solution

首先显然我们一定走过的路径是$AE+EF+FD$, 其中$E,F$分别是$AB, CD$上的动点.

我们设$dis(A,B)$表示$A \to B$的最短距离, $(A, B)$表示直线$AB$, 那么答案就是:

$$\min_{E \in (A, B), F \in (C, D)} \frac{dis(A, E)}{p} + \frac{dis(E, F)}{r} + \frac {dis(F,D)}{q}$$

这是一个二元函数, 求其极值比较麻烦, 那么我们考虑主元法, 设$F$为主元, 也就是在原方程中把$E$当成常数处理.

那么这里的未知数就是$F$, 原函数可以转化为:

$$f(E) = \min_{F \in (C,D)} \frac{dis(E,F)}{r} + \frac{dis(F, D)}{q}$$

根据小学奥数 - 将军饮马问题, 我们可以知道这个单峰函数, 求其极值可以使用三分法.

三分$F$的坐标就可以得到以$F$为主元的最小函数值.

那么我们如何取得$\frac{dis(A, E)}{p} + f(E)$的最小值呢.

还是根据将军饮马问题, 我们可以得到这还是个单峰函数, 那么我们继续用三分法求极值.

综上, 三分套三分求解即可.

Code

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/* Headers */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const double eps = 1e-8;
double ax, ay, bx, by, cx, cy, dx, dy, p, q, r;
/* functions */
inline double dis(double x1, double y1, double x2, double y2) {
	double x = x1 - x2,  y = y1 - y2;
	return std::sqrt(x * x + y * y);
}
inline double f(double x1, double y1, double x2, double y2) {
	return dis(x1, y1, x2, y2) / r + dis(x2, y2, dx, dy) / q; 
}
inline double TrisectIn(double x, double y) {
	double lx = cx, ly = cy, rx = dx, ry = dy;
	while(dis(lx, ly, rx, ry) > eps) {
		double tmpx = (rx - lx) / 3, tmpy = (ry - ly) / 3;
		double lmidx = lx + tmpx, rmidx = rx - tmpx;
		double lmidy = ly + tmpy, rmidy = ry - tmpy;
		double ans1 = f(x, y, lmidx, lmidy), ans2 = f(x, y, rmidx, rmidy);
		if(ans2 - ans1 > eps) rx = rmidx, ry = rmidy;
		else lx = lmidx, ly = lmidy;
	}
	return f(x, y, lx, ly);
}
inline double TrisectOut() {
	double lx = ax, ly = ay, rx = bx, ry = by;
	while(dis(lx, ly, rx, ry) > eps) {
		double tmpx = (rx - lx) / 3, tmpy = (ry - ly) / 3;
		double lmidx = lx + tmpx, rmidx = rx - tmpx;
		double lmidy = ly + tmpy, rmidy = ry - tmpy;
		double ans1 = TrisectIn(lmidx, lmidy) + dis(ax, ay, lmidx, lmidy) / p;
		double ans2 = TrisectIn(rmidx, rmidy) + dis(ax, ay, rmidx, rmidy) / p;
		if(ans2 - ans1 > eps) rx = rmidx, ry = rmidy;
		else lx = lmidx, ly = lmidy;
	}
	return TrisectIn(lx, ly) + dis(ax, ay, lx, ly) / p;
}
int main(int argc,char *argv[]){
	scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy, &p, &q, &r);
	printf("%.2lf\n", TrisectOut());
	return 0;
}

THE END