Description

題庫鏈接

在一個 \(2\) 維平面上有兩條傳送帶，每一條傳送帶可以看成是一條線段。兩條傳送帶分別為線段 \(AB\) 和線段 \(CD\) 。在 \(AB\) 上的移動速度為 \(P\) ，在 \(CD\) 上的移動速度為 \(Q\) ，在平面上的移動速度 \(R\) 。現在從 \(A\) 點走到 \(D\) 點，他想知道最少需要走多長時間。

\(1\leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\leq 1000,1\leq P,Q,R\leq 10\)

Solution

我們大膽猜想不用求證小心求證。我們猜測當我們來枚舉在 \(AB\) 上的離開點和 \(CD\) 上的進入點時，是兩個單峰函數。

那么直接用三分法求解了。注意要特判線段退化成點的情況。

至于證明，都說了不用求證小心求證。詳見鏈接：->戳我<-

Code

//It is made by Awson on 2018.3.1 #include <bits/stdc++.h> #define LL long long #define dob complex<double> #define Abs(a) ((a) < 0 ? (-(a)) : (a)) #define Max(a, b) ((a) > (b) ? (a) : (b)) #define Min(a, b) ((a) < (b) ? (a) : (b)) #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b)) #define writeln(x) (write(x), putchar('\n')) #define lowbit(x) ((x)&(-(x))) using namespace std; const double eps = 1e-4; void read(int &x) {char ch; bool flag = 0;for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());x *= 1-2*flag; } void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); } void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }double xa, ya, xb, yb, xc, yc, xd, yd, p, q, r, ans; double e, f, g, h, i, j;double dist(double a, double b, double c, double d) { #define sqr(x) ((x)*(x))double ans = 0;ans += sqrt(sqr(a-e)+sqr(b-f))/p;ans += sqrt(sqr(a-c)+sqr(b-d))/r;ans += sqrt(sqr(c-g)+sqr(d-h))/q;return ans; } double count(double x, double y) {xc = i, yc = j, xd = g, yd = h;double ans = dist(x, y, xd, yd);while (true) {if (fabs(yc-yd) <= eps && fabs(xc-xd) <= eps) break;double xm1 = (xc*2+xd)/3., xm2 = (xc+xd*2)/3.;double ym1 = (yc*2+yd)/3., ym2 = (yc+yd*2)/3.;double c1 = dist(x, y, xm1, ym1), c2 = dist(x, y, xm2, ym2);if (c1 > c2) xc = xm1, yc = ym1, ans = c2; else xd = xm2, yd = ym2, ans = c1;}return ans; } void work() {scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf", &xa, &ya, &xb, &yb, &xc, &yc, &xd, &yd, &p, &q, &r);e = xa, f = ya, g = xd, h = yd, i = xc, j = yc; ans = count(xa, ya);while (true) {if (fabs(ya-yb) <= eps && fabs(xa-xb) <= eps) break;double xm1 = (xa*2+xb)/3., xm2 = (xa+xb*2)/3.;double ym1 = (ya*2+yb)/3., ym2 = (ya+yb*2)/3.;double c1 = count(xm1, ym1), c2 = count(xm2, ym2);if (c1 > c2) xa = xm1, ya = ym1, ans = c2; else xb = xm2, yb = ym2, ans = c1;}printf("%.2lf\n", ans); } int main() {work(); return 0; }

轉載于:https://www.cnblogs.com/NaVi-Awson/p/8486832.html

總結

以上是生活随笔為你收集整理的[SCOI 2010]传送带的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。