題目描述

原題來自：SCOI 2010

在一個 2 維平面上有兩條傳送帶，每一條傳送帶可以看成是一條線段。兩條傳送帶分別為線段? AB和線段CD 。lxhgww 在? AB上的移動速度為 P ，在? CD上的移動速度為 Q ，在平面上的移動速度R 。

現(xiàn)在 lxhgww 想從A? 點走到 D 點，他想知道最少需要走多長時間。

輸入格式

輸入數(shù)據(jù)第一行是4? 個整數(shù)，表示? A和? B的坐標，分別為?；;

第二行是 4 個整數(shù)，表示??和??的坐標，分別為?，；;

第三行是? 3個整數(shù)，分別是?。P,Q,R.

輸出格式

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

樣例

樣例輸入

0 0 0 100 100 0 100 100 2 2 1

樣例輸出

136.60

描述：emmmm，看完之后，第一反應(yīng)是暴力做，wa了幾發(fā)之后，才曉得用三分套三分，果然不能輕視每一個算法啊。

分析：

給到四個點，我們可以分到最多三個線段。三分ab上的點到得到線段，將改點代入再三分cd上的點得到線段；用返回值（P,Q,R，分別為線段AB，線段CD，平地上的速度）,來判斷兩個點是不是最優(yōu)點。

上代碼：

#include<stdio.h> #include<math.h> #include<string.h> #include<algorithm> using namespace std; const double eps=1e-4; int m,n,k,a1,a2,b1,b2,c1,c2,d1,d2; double dfs(double x1,double y1,double x2,double y2) {return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double bfs(double x,double y) {double cx=c1, cy=c2,dx=d1, dy=d2,ab=dfs(a1,a2,x,y)/m;while(fabs(dx-cx)>eps||fabs(dy-cy)>eps){double x1=cx+(dx-cx)/3,x2=dx-(dx-cx)/3;double y1=cy+(dy-cy)/3,y2=dy-(dy-cy)/3;double s1=ab+dfs(x,y,x1,y1)/k+dfs(x1,y1,d1,d2)/n;double s2=ab+dfs(x,y,x2,y2)/k+dfs(x2,y2,d1,d2)/n;if(s1<=s2)dx=x2,dy=y2;elsecx=x1,cy=y1;}return ab+dfs(x,y,cx,cy)/k+dfs(cx,cy,d1,d2)/n; } int main() {scanf("%d%d%d%d",&a1,&a2,&b1,&b2);scanf("%d%d%d%d",&c1,&c2,&d1,&d2);scanf("%d%d%d",&m,&n,&k);double ax=a1,ay=a2,bx=b1,by=b2;while(fabs(bx-ax)>eps||fabs(by-ay)>eps){double x1=ax+(bx-ax)/3,x2=bx-(bx-ax)/3;double y1=ay+(by-ay)/3,y2=by-(by-ay)/3;if(bfs(x1,y1)<=bfs(x2,y2))bx=x2,by=y2;elseax=x1,ay=y1;}printf("%.2lf\n",bfs(ax,ay));return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的#10017 「一本通 1.2 练习 4」传送带+三分套三分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。