傳送帶

Time Limit:?1 Sec??Memory Limit:?64 MB
[Submit][Status][Discuss]

Description

　　在一個(gè)2維平面上有兩條傳送帶，每一條傳送帶可以看成是一條線段。兩條傳送帶分別為線段AB和線段CD。lxhgww在AB上的移動(dòng)速度為P，在CD上的移動(dòng)速度為Q，在平面上的移動(dòng)速度R。現(xiàn)在lxhgww想從A點(diǎn)走到D點(diǎn)，他想知道最少需要走多長(zhǎng)時(shí)間

Input

　　輸入數(shù)據(jù)第一行是4個(gè)整數(shù)，表示A和B的坐標(biāo)，分別為Ax，Ay，Bx，By 第二行是4個(gè)整數(shù)，表示C和D的坐標(biāo)，分別為Cx，Cy，Dx，Dy 第三行是3個(gè)整數(shù)，分別是P，Q，R

Output

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

Sample Input

　　0 0 0 100
　　100 0 100 100
　　2 2 1

Sample Output

　　136.60

HINT

　　對(duì)于100%的數(shù)據(jù)，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
　　1<=P，Q，R<=10

Main idea

　　給定平面上的兩條線段AB,CD，在AB,CD上移動(dòng)會(huì)有一個(gè)特別的速度，在平面上移動(dòng)會(huì)有一個(gè)速度，求從點(diǎn)A到點(diǎn)D的最短時(shí)間。

Solution

　　首先發(fā)現(xiàn)坐標(biāo)范圍-1000~1000，并且精度要求不高，從此基礎(chǔ)上思考。我們先考慮從AB上一個(gè)定點(diǎn)O到CD上的距離，發(fā)現(xiàn)其中從O到CD的距離是先減小再增大的，我們大膽猜測(cè)這道題的答案滿足單峰性。然后我們可以用三分（效率為O(log1.5(n))）來(lái)實(shí)現(xiàn)。
　　我們現(xiàn)在可以求出一個(gè)定點(diǎn)求CD的最短時(shí)間，這里用三分實(shí)現(xiàn)。然后怎么辦呢？
　　由于AB也是一條線段，我們大膽猜測(cè)，可以再在AB上三分一個(gè)點(diǎn)，這樣就是三分套三分，最后發(fā)現(xiàn)其正確性可以證明。
　　三分方法（這里給出求最小值的方法）：在區(qū)間1/3處和2/3處各取兩個(gè)點(diǎn)l,r，如果左段（即L~l）的答案比右段（r~R）的更優(yōu)，那么由于單峰性（圖像類似一個(gè)拋物線）可以抹去右段，多次操作使得答案最優(yōu)。

Code

1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 10 const int ONE=1005; 11 const int MOD=19650827; 12 13 int n; 14 15 struct power 16 { 17 double x,y; 18 double AB,CD,PM; 19 friend power operator +(power a,power b) {a.x=a.x+b.x; a.y=a.y+b.y; return a;} 20 friend power operator -(power a,power b) {a.x=a.x-b.x; a.y=a.y-b.y; return a;} 21 22 }; 23 power A,B,C,D,v; 24 power l1,l2,r1,r2; 25 power a,b; 26 power pass; 27 28 int get() 29 { 30 int res,Q=1; char c; 31 while( (c=getchar())<48 || c>57) 32 if(c=='-')Q=-1; 33 if(Q) res=c-48; 34 while((c=getchar())>=48 && c<=57) 35 res=res*10+c-48; 36 return res*Q; 37 } 38 39 double dist(power a,power b) 40 { 41 return (double)sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); 42 } 43 44 double Getdist(power E,power F) 45 { 46 return dist(A,E)/v.AB + dist(E,F)/v.PM + dist(F,D)/v.CD; 47 } 48 49 double Trivide(power O) 50 { 51 power l=C,r=D,pass,a,b; 52 while(dist(l,r)>0.001) 53 { 54 pass.x=(r.x-l.x)/3.0; pass.y=(r.y-l.y)/3.0; 55 a=l+pass; b=r-pass; 56 if(Getdist(O,a) < Getdist(O,b)) r=b; 57 else l=a; 58 } 59 return Getdist(O,l); 60 } 61 62 int main() 63 { 64 scanf("%lf %lf %lf %lf",&A.x,&A.y,&B.x,&B.y); 65 scanf("%lf %lf %lf %lf",&C.x,&C.y,&D.x,&D.y); 66 scanf("%lf %lf %lf",&v.AB,&v.CD,&v.PM); 67 68 power l=A,r=B; 69 while(dist(l,r)>0.001) 70 { 71 pass.x=(r.x-l.x)/3.0; pass.y=(r.y-l.y)/3.0; 72 a=l+pass; b=r-pass; 73 if(Trivide(a) < Trivide(b)) r=b; 74 else l=a; 75 } 76 77 printf("%.2lf",Trivide(l)); 78 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/BearChild/p/6441257.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ1857】【SCOI2010】传送带 [三分]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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