【HDU 3400】Line belt（三分法）

旧城等待， 2023-06-01 14:57 29阅读 0赞

### 题目链接 ###

[题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=3400][http_acm.hdu.edu.cn_showproblem.php_pid_3400]

### 题意 ###

有两条传送带AB和CD，移动速度分别为p，q。  
除了传送带的其他区域移动速度为r，问A到D最短时间。

### 题目分析 ###

1.  在AB上找一点E，在CD上找一点F。
2.  使得A->E->F->D时间最短。

### 数学思路 ###

时间 time = |AE|/p + |EF|/r + |FD|/q。 （|AE|为线段AE的长度。）

未知量有E的位置和F的位置，由于确定在AB和CD上，所以只需要两个未知量|AE|和|FD|。

一般采用拉格朗日乘数法，可以求出最值。

但是用这个方法解题貌似不太方便，所以有了下面的三分法。

### 解题思路 ###

1.  对AB三分，mid1和mid2为分点。
2.  固定mid1对CD进行三分，固定mid2对CD进行三分。
3.  mid1得到时间t1，mid2得到时间t2.
4.  不断三分直到两次求得时间之差abs(t1-t2)达到一定精度。

### 三分法 ###

三分法是求某个区间内的极值点的算法。

[二、三分法详解][Link 1]

### 代码如下（G++） ###

#include <bits\stdc++.h> using namespace std; typedef long long ll; double eps = 1e-6; int p, q, r; int ax, ay, bx, by, cx, cy, dx, dy; double min(double x, double y) { return x < y ? x : y; } double findCD(double ABx, double ABy) { double lx = cx; double ly = cy; double rx = dx; double ry = dy; double mid1x, mid1y, mid2x, mid2y; double time1 = 0, time2 = 0; do { mid1x = lx + (rx - lx) / 3; mid1y = ly + (ry - ly) / 3; mid2x = lx + 2 * (rx - lx) / 3; mid2y = ly + 2 * (ry - ly) / 3; time1 = sqrt((dx - mid1x) * (dx - mid1x) + (dy - mid1y) * (dy - mid1y)) / q + sqrt((ABx - mid1x) * (ABx - mid1x) + (ABy - mid1y) * (ABy - mid1y)) / r; time2 = sqrt((dx - mid2x) * (dx - mid2x) + (dy - mid2y) * (dy - mid2y)) / q + sqrt((ABx - mid2x) * (ABx - mid2x) + (ABy - mid2y) * (ABy - mid2y)) / r; if (time1 < time2) { rx = mid2x; ry = mid2y; } else { lx = mid1x; ly = mid1y; } } while (abs(time1 - time2) > eps); return time1; } //三分AB double findAB() { double lx = ax; double ly = ay; double rx = bx; double ry = by; double mid1x, mid1y, mid2x, mid2y; double time1 = 0, time2 = 0; do { mid1x = lx + (rx - lx) / 3; mid1y = ly + (ry - ly) / 3; mid2x = lx + 2 * (rx - lx) / 3; mid2y = ly + 2 * (ry - ly) / 3; //三分CD time1 = sqrt((ax - mid1x) * (ax - mid1x) + (ay - mid1y) * (ay - mid1y)) / p + findCD(mid1x, mid1y); time2 = sqrt((ax - mid2x) * (ax - mid2x) + (ay - mid2y) * (ay - mid2y)) / p + findCD(mid2x, mid2y); if (time1 < time2) { rx = mid2x; ry = mid2y; } else { lx = mid1x; ly = mid1y; } } while (abs(time1 - time2) > eps); return time1; } int main() { int t; cin >> t; while (t--) { cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy; cin >> p >> q >> r; printf("%.2lf\n", findAB()); } return 0; }

转载于:https://www.cnblogs.com/zhangjiuding/p/11470650.html

[http_acm.hdu.edu.cn_showproblem.php_pid_3400]: http://acm.hdu.edu.cn/showproblem.php?pid=3400
[Link 1]: https://blog.csdn.net/u012469987/article/details/50897291