题目描述
在一个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
输出格式：输出数据为一行，表示lxhgww从A点走到D点的最短时间，保留到小数点后2位
输入输出样例
输入样例#1：
0 0 0 100
100 0 100 100
2 2 1
输出样例#1：
136.60
说明
对于100%的数据，1<= Ax，Ay，Bx，By，Cx，Cy，Dx，Dy<=1000
Solution：
本题正解是三分法，然而不会用，考试时随便打了个退火水了70，后面调了一下就A了。
退火的思路就比较简单，预处理出初值$ans$为四条路径中的最小值：$(1)A ightarrow D;(2)A ightarrow B ightarrow D;(3)A ightarrow C ightarrow D;(4)A ightarrow B ightarrow C ightarrow D$。
然后对于四种路径，我们都能固定一条边而在另一边中枚举点。比如在$AB$中枚举中点，每次就算出答案后更新，若不优于当前解，则有一定概率还是往该方向移动，至于移动的具体方向，我也不知道，所以就强行rand了（什么鬼？这样子都能A），每次都找中点，直到两个边界点特别接近（弄个exp）。
最后再强行退火100次，就好了（退火太玄学，反正AC就是正解）。
代码：
#include<bits/stdc++.h> #pragma GCC optimize(2) #define il inline #define ll long long #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--) using namespace std; const double R=0.98,Exp=1e-5; double ax,ay,bx,by,cx,cy,dx,dy,p,q,r,ans; int main(){ srand(time(0)); 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 ab=sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by)); double cd=sqrt((cx-dx)*(cx-dx)+(cy-dy)*(cy-dy)); double ac=sqrt((ax-cx)*(ax-cx)+(ay-cy)*(ay-cy)); double bc=sqrt((bx-cx)*(bx-cx)+(by-cy)*(by-cy)); double ad=sqrt((ax-dx)*(ax-dx)+(ay-dy)*(ay-dy)); double bd=sqrt((bx-dx)*(bx-dx)+(by-dy)*(by-dy)); ans=ad/r; ans=min(ans,ab/p+bd/r); ans=min(ans,ab/p+bc/r+cd/q); ans=min(ans,ac/r+cd/q); For(i,1,100){ double tx=ax,ty=ay,px=bx,py=by,mx,my,T=5201314; while(sqrt((tx-px)*(tx-px)+(ty-py)*(ty-py))>0.01){ mx=(tx+px)/2,my=(ty+py)/2; double fu=sqrt((mx-ax)*(mx-ax)+(my-ay)*(my-ay))/p+sqrt((mx-dx)*(mx-dx)+(my-dy)*(my-dy))/r; if(fu<ans){ ans=fu; if(rand()%2) tx=mx,ty=my; else px=mx,py=my; } else { if(rand()<T) { if(rand()%2)tx=mx,ty=my; else px=mx,py=my; T*=R; } } } tx=cx,ty=cy,px=dx,py=dy,T=5201314; while(sqrt((tx-px)*(tx-px)+(ty-py)*(ty-py))>0.01){ mx=(tx+px)/2,my=(ty+py)/2; double fu=sqrt((mx-ax)*(mx-ax)+(my-ay)*(my-ay))/r+sqrt((mx-dx)*(mx-dx)+(my-dy)*(my-dy))/q; if(fu<ans){ ans=fu; if(rand()%2) tx=mx,ty=my; else px=mx,py=my; } else { if(rand()<T) { if(rand()%2)tx=mx,ty=my; else px=mx,py=my; T*=R; } } } tx=ax,ty=ay,px=bx,py=by,mx,my,T=5201314; while(sqrt((tx-px)*(tx-px)+(ty-py)*(ty-py))>0.01){ mx=(tx+px)/2,my=(ty+py)/2; double fu=sqrt((mx-ax)*(mx-ax)+(my-ay)*(my-ay))/p+sqrt((mx-cx)*(mx-cx)+(my-cy)*(my-cy))/r+cd/q; if(fu<ans){ ans=fu; if(rand()%2) tx=mx,ty=my; else px=mx,py=my; } else { if(rand()<T) { if(rand()%2)tx=mx,ty=my; else px=mx,py=my; T*=R; } } } tx=cx,ty=cy,px=dx,py=dy,T=5201314; while(sqrt((tx-px)*(tx-px)+(ty-py)*(ty-py))>0.01){ mx=(tx+px)/2,my=(ty+py)/2; double fu=sqrt((mx-bx)*(mx-bx)+(my-by)*(my-by))/r+sqrt((mx-dx)*(mx-dx)+(my-dy)*(my-dy))/q+ab/p; if(fu<ans){ ans=fu; if(rand()%2) tx=mx,ty=my; else px=mx,py=my; } else { if(rand()<T) { if(rand()%2)tx=mx,ty=my; else px=mx,py=my; T*=R; } } } } printf("%.2lf",ans); return 0; }