題目描述

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

輸入輸出格式

輸入格式：

輸入數據第一行是4個整數，表示A和B的坐標，分別為Ax，Ay，Bx，By

第二行是4個整數，表示C和D的坐標，分別為Cx，Cy，Dx，Dy

第三行是3個整數，分別是P，Q，R

對于100%的數據，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000，1<=P，Q，R<=10

輸出格式：

輸出數據為一行，表示lxhgww從A點走到D點的最短時間，保留到小數點后2位

輸入輸出樣例

輸入樣例#1：

0 0 0 100
100 0 100 100
2 2 1

輸出樣例#1：

136.60

思路：

假設從 AB 上一點 E 開始走向 CD ，到達 CD 的 F 點，那么 AE+EF+FD 就是走的總路程

假設 AB 上的 E 點固定，那么對于另一個點 F 來說，顯然該點存在最小值，是一個單峰函數，此時可利用三分來求出這個點

同理，將 F 點固定后，對另一個點 E，也存在最小值，因此不能單獨的三分 E 點或 F 點，要同時三分

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const double EPS = 1E-10; const int MOD = 1E9+7; const int N = 10000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; struct Node{double x,y;Node(){}Node(double x,double y):x(x),y(y){} }a,b,c,d; double p,q,r; double getDis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double judge(Node e){Node left(c.x,c.y);Node right(d.x,d.y);int times=100;//控制三分次數while(times--){Node lmid,rmid;lmid.x=left.x+(right.x-left.x)/3;lmid.y=left.y+(right.y-left.y)/3;rmid.x=right.x-(right.x-left.x)/3;rmid.y=right.y-(right.y-left.y)/3;double dis1=getDis(lmid.x,lmid.y,d.x,d.y)/q+getDis(lmid.x,lmid.y,e.x,e.y)/r;double dis2=getDis(rmid.x,rmid.y,d.x,d.y)/q+getDis(rmid.x,rmid.y,e.x,e.y)/r;if(dis1<dis2){right.x=rmid.x;right.y=rmid.y;}else{left.x=lmid.x;left.y=lmid.y;}}return getDis(left.x,left.y,d.x,d.y)/q+getDis(left.x,left.y,e.x,e.y)/r+getDis(e.x,e.y,a.x,a.y)/p;} int main(){scanf("%lf%lf",&a.x,&a.y);scanf("%lf%lf",&b.x,&b.y);scanf("%lf%lf",&c.x,&c.y);scanf("%lf%lf",&d.x,&d.y);scanf("%lf%lf%lf",&p,&q,&r);Node left(a.x,a.y);Node right(b.x,b.y);int times=100;//控制三分次數while(times--){Node lmid,rmid;lmid.x=left.x+(right.x-left.x)/3;lmid.y=left.y+(right.y-left.y)/3;rmid.x=right.x-(right.x-left.x)/3;rmid.y=right.y-(right.y-left.y)/3;if(judge(lmid)<judge(rmid)){right.x=rmid.x;right.y=rmid.y;}else{left.x=lmid.x;left.y=lmid.y;}}printf("%.2lf",judge(left));return 0; }

?

總結

以上是生活随笔為你收集整理的传送带（洛谷-P2571）的全部內容，希望文章能夠幫你解決所遇到的問題。

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