「BZOJ1857」[Scoi2010]传送带

Description

在一个22维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段ABAB和线段CDCD。lxhgww在ABAB上的移动速度为PP,在CDCD上的移动速度为QQ,在平面上的移动速度RR。现在lxhgww想从AA点走到DD点,他想知道最少需要走多长时间

Input

输入数据第一行是44个整数,表示AABB的坐标,分别为AxA_xAyA_yBxB_xByB_y
第二行是44个整数,表示CCDD的坐标,分别为Cx,Cy,Dx,Dy
第三行是33个整数,分别是PPQQRR

Output

输出数据为一行,表示lxhgww从AA点走到DD点的最短时间,保留到小数点后22

Sample Input

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

Sample

1
136.60

HINT

对于100%100\%的数据,1Ax,Ay,Bx,By,Cx,Cy,Dx,Dy10001\leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\leq 1000
1P,Q,R101\leq P,Q,R\leq10

Solution

假设在线段ABAB走的距离是x0x_0,线段CDCD走的距离是x1x_1
可以求出三段线段的长度然后计算时间。长度用三角函数求,注意d=0d=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
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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<bitset>
#define mk make_pair
#define fi first
#define sqr(x) ((x)*(x))
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
struct Point {
double x, y;
}a[4];
const int N = 210;
struct Linz {
double x[2], y, v[2], mx[2], my;
}p[N],g;
double randd() {
return (double) rand() / RAND_MAX;
}
double dist(double x1, double y1, double x2, double y2) {
return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}
const int T = 20;
double P, Q, R;
double d[2];
double tx1,tx2,ty1,ty2;

double cal(Linz p) {
double t1 = p.x[0] / P ;
double t2 = p.x[1] / Q;
return t1 + t2 + dist(a[0].x + p.x[0] * tx1, a[0].y + p.x[0] * ty1, a[3].x - p.x[1] * tx2, a[3].y - p.x[1] * ty2) / R;
}
void init() {
d[0] =dist(a[0].x, a[0].y, a[1].x,a[1].y);
d[1] = dist(a[2].x,a[2].y, a[3].x,a[3].y);
if(fabs(d[0]) > 1e-8) {
tx1 = (a[1].x - a[0].x) / d[0];
ty1 = (a[1].y - a[0].y) / d[0];
}
if(fabs(d[1]) > 1e-8) {
tx2 = (a[3].x - a[2].x) / d[1];
ty2 = (a[3].y - a[2].y) / d[1];
}
g.my = 1e99;
for(int i = 1; i <= T; ++i) {
p[i].mx[0] = p[i].x[0] = randd() * d[0];
p[i].mx[1] = p[i].x[1] = randd() * d[1];
p[i].my = p[i].y = cal(p[i]);
if(p[i].my < g.my) g = p[i];
}
}
void run() {
for(int i = 1; i <= T; ++i) {
for(int j = 0; j < 2; ++j) {
p[i].v[j] = p[i].v[j] * 0.4 + (p[i].mx[j] - p[i].x[j]) * randd() * 2+ (g.mx[j] - p[i].x[j]) * randd() * 2;
if(p[i].v[j]>d[j]) p[i].v[j] = d[j];
p[i].x[j] += p[i].v[j];
if(p[i].x[j] < 0) p[i].x[j] = 0, p[i].v[j] = -p[i].v[j];
if(p[i].x[j] > d[j]) p[i].x[j] = d[j], p[i].v[j] = -p[i].v[j];
}
p[i].y = cal(p[i]);
if(p[i].y < p[i].my) {
p[i].my = p[i].y;
for(int j = 0; j < 2; ++j) p[i].mx[j] = p[i].x[j];
}
}
for(int i = 1; i <= T; ++i)
if(g.my > p[i].my) g = p[i];
}
int main() {
for(int i = 0; i < 4; ++i) scanf("%lf%lf",&a[i].x, &a[i].y);
scanf("%lf%lf%lf",&P, &Q,&R);
init();
for(int i = 1; i <= 100; ++i)
run();
printf("%.2lf", g.my);
return 0;
}