傳送帶 方法記錄
- 2022 年 11 月 7 日
- 筆記
[SCOI2010]傳送帶
題目描述
在一個 \(2\) 維平面上有兩條傳送帶，每一條傳送帶可以看成是一條線段。兩條傳送帶分別為線段 \(\text{AB}\) 和線段 \(\text{CD}\)。lxhgww 在 \(\text{AB}\) 上的移動速度為 \(P\)，在 \(\text{CD}\) 上的移動速度為 \(Q\)，在平面上的移動速度 \(R\)。現在 lxhgww 想從 \(\text A\) 點走到 \(\text D\) 點，他想知道最少需要走多長時間。
輸入格式
第一行 \(4\) 個整數，表示 \(\text A\) 和 \(\text B\) 的坐標，分別為 \(A_x\)，\(A_y\)，\(B_x\)，\(B_y\)。
第二行 \(4\) 個整數，表示 \(\text C\) 和 \(\text D\) 的坐標，分別為 \(C_x\)，\(C_y\)，\(D_x\)，\(D_y\)。
第三行 \(3\) 個整數，分別是 \(P\)，\(Q\)，\(R\)。
輸出格式
輸出數據為一行，表示 lxhgww 從 \(\text A\) 點走到 \(\text D\) 點的最短時間，保留到小數點後 \(2\) 位。
樣例 #1
樣例輸入 #1
0 0 0 100
100 0 100 100
2 2 1
樣例輸出 #1
136.60
提示
對於 \(100\%\) 的數據，\(1\le A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y\le10^3\)，\(1\le P,Q,R\le10\)。
題解
涉及到精度的問題確實還沒什麼經驗啊。
考試的時候，我第一反應是胡不歸問題，但數據不允許用胡不歸的任何結論。然後思考的方向就轉表成了計算幾何，最終打了個偽的三分。
解題的關鍵在於分析路線
在線段\(AB\)上取一點\(P1\),在線段\(CD\)上取一點\(P2\),那麼運動路線就是\(A\)->\(P1\)->\(P2\)->\(D\).
枚舉法
由於題目對精度的要求比較小（只保留兩位小數），所以接下來的策略就是枚舉\(P1\),\(P2\)在各自線段上的位置，即枚舉兩個轉折點。
具體地，我們將兩條線段分為若干等份（分的份數越多，精度越高，用的時間也越長），然後二維枚舉每一對等分點，計算出在這兩個點轉折，總路程花費的時間，並統計出最小的時間。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double eps=0.00025;
double ax,ay,bx,by,cx,cy,dx,dy;
double p,q,r;
double ans=1e9;
double get_tim(double x1,double y1,double x2,double y2)
{
double s1=sqrt((x1-ax)*(x1-ax)+(y1-ay)*(y1-ay));
double s2=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
double s3=sqrt((dx-x2)*(dx-x2)+(dy-y2)*(dy-y2));
double res=s1*1.0/p+s2*1.0/r+s3*1.0/q;
return res;
}
int main()
{
freopen("tran.in","r",stdin);
freopen("tran.out","w",stdout);
scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
scanf("%lf%lf%lf",&p,&q,&r);
for(double mul1=0;mul1<=1;mul1+=eps)
{
for(double mul2=0;mul2<=1;mul2+=eps)
{
double x1=ax+(bx-ax)*1.0*mul1;
double y1=ay+(by-ay)*1.0*mul1;
double x2=cx+(dx-cx)*1.0*mul2;
double y2=cy+(dy-cy)*1.0*mul2;
ans=min(ans,get_tim(x1,y1,x2,y2));
}
}
printf("%.2lf\n",ans);
return 0;
}
當然，本題還有另外一種做法：三分法
三分法
路徑分析的方法不變，即依然以「運動路線為\(A\)->\(P1\)->\(P2\)->\(D\).」進行思考。
使用三分法之前，先考慮函數的凸性。（不算是證明，頂多算感性理解）
從起點開始，先在線段上行走一段時間，再在平面上行走一段時間，線段和平面上的速度不一樣。
我們將從起點開始，在線段上行走的這段距離設為 \(x\) ,運動的總時間設為 \(tim\) .
\(PART 1\)
先考慮比較刁鑽的情況，平面速度大於線段速度。
這種情況下，只走平面無疑是最明智的。因為走線段又慢又繞路，吃力不討好。\(x\) 與 \(tim\) 的函數影像就是單調函數（實質上是單峰函數的一半）。
但這種情況仍然可以使用三分法，因為最終決策點會被逐漸推向起點處，所以三分法在對上這種情況時仍有正確性。（這也是為什麼說看似單調函數的影像實質上是單峰函數的一半）
\(PART 2\)
接下來再考慮，平面速度小於線段速度。
這時候我們就可以選擇性地走線段了。由於三角形的性質，剛開始的時候走線段會產生正收益，但當前位置與終點連線的斜率逐漸減小，正收益會逐漸降低，最終變為負收益。而這個由正收益轉變為負收益的拐點，就是使全程用時最小的轉折點。
而\(x\) 與 \(tim\) 的函數影像就是單峰函數。
接下來就可以使用三分法了。
由於我們需要做出兩個決策，分別是兩條線段上的轉折點，所以我們考慮先用三分法選定一條線段上的某個轉折點，再用三分法選擇另一條線段上的某個轉折點。這將會是一個三分套三分的樣式。
方便起見，我們三分的對象是部分佔總體的比例。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-12;
double ax,ay,bx,by,cx,cy,dx,dy;
double p,q,r;
double ans=1e9;
double get_tim(double k1,double k2)//選出兩個情況，計算時間
{
double x1=(bx-ax)*k1+ax;
double y1=(by-ay)*k1+ay;
double x2=(dx-cx)*k2+cx;
double y2=(dy-cy)*k2+cy;
double s1=sqrt((x1-ax)*(x1-ax)+(y1-ay)*(y1-ay));
double s2=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
double s3=sqrt((dx-x2)*(dx-x2)+(dy-y2)*(dy-y2));
double res=s1*1.0/p+s2*1.0/r+s3*1.0/q;
return res;
}
double get_ant(double k)//選定一條邊上的情況後選擇另一條邊上的情況
{
double l=0,r=1;
while(r-l>=eps)
{
double ml=l+(r-l)/3.0;
double mr=r-(r-l)/3.0;
if(get_tim(k,ml)<get_tim(k,mr)) r=mr;
else l=ml;
}
return get_tim(k,l);
}
int main()
{
freopen("tran.in","r",stdin);
freopen("tran.out","w",stdout);
scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
scanf("%lf%lf%lf",&p,&q,&r);
double l=0,r=1;
while(r-l>=eps)
{
double ml=l+(r-l)/3.0;
double mr=r-(r-l)/3.0;
if(get_ant(ml)<get_ant(mr)) r=mr;
else l=ml;
}
printf("%.2lf\n",get_ant(l));
return 0;
}
使用三分法可以減少枚舉次數，使得用時明顯減少，在對上更大的數據時，三分法的優勢也會更加顯著。
