NC 20276 [SCOI2010] 三分

题意

传送门 NC 20276 [SCOI2010]传送带

题解

路径只有传送带 $AB,CD$ 以及平面移动 $3$ 种选择。设在传送带 $AB,CD$ 移动的距离分别与自身长度的比值为 $t_1,t_2$，分别移动至传送带上的端点 $E,F$，则总时间为

$$T=\frac{d_{AB}{t}_1}{P}+\frac{d_{CP}{t}_2}{Q}+\frac{d_{EF}}{R}$$

观察到总时间是关于 $t1,t2$ 的二元二次函数，则三分法求 $t1$，检验函数三分 $t2$ 求已知 $t1$ 时，$T$ 的最小值。

#include <bits/stdc++.h> using namespace std; struct point { int x, y; } A, B, C, D; int P, Q, R; double Dab, Dcd, a, b, c, d, e, f; double dist(double x1, double y1, double x2, double y2) { double dx = x1 - x2, dy = y1 - y2; return sqrt(dx * dx + dy * dy); } double judge(double x) { double lb = 0, ub = 1; for (int i = 0; i < 100; i++) { double mid = (lb + ub) / 2, mmid = (mid + ub) / 2; double c1 = Dcd * mid / Q + dist(a + b * x + c * mid, d + e * x + f * mid, 0, 0) / R; double c2 = Dcd * mmid / Q + dist(a + b * x + c * mmid, d + e * x + f * mmid, 0, 0) / R; if (c1 < c2) ub = mmid; else lb = mid; } return Dab * x / P + Dcd * lb / Q + dist(a + b * x + c * lb, d + e * x + f * lb, 0, 0) / R; } int main() { scanf("%d%d%d%d", &A.x, &A.y, &B.x, &B.y); scanf("%d%d%d%d", &C.x, &C.y, &D.x, &D.y); scanf("%d%d%d", &P, &Q, &R); Dab = dist(A.x, A.y, B.x, B.y), Dcd = dist(C.x, C.y, D.x, D.y); a = A.x - D.x, b = B.x - A.x, c = D.x - C.x, d = A.y - D.y, e = B.y - A.y, f = D.y - C.y; double lb = 0, ub = 1; for (int i = 0; i < 100; i++) { double mid = (lb + ub) / 2, mmid = (mid + ub) / 2; if (judge(mid) < judge(mmid)) ub = mmid; else lb = mid; } printf("%.2f\n", judge(lb)); return 0; }