题解 P2571 【[SCOI2010]传送带】
浅色调
·
·
题解
Solution：
本题正解是三分法，然而不会用，考试时随便打了个模拟退火水了70分，后面调了一下就AC了。
退火的思路就比较简单，预处理出初值$ans$为四条路径中的最小值：$(1)A\rightarrow D\;(2)A\rightarrow B\rightarrow D\;(3)A\rightarrow C\rightarrow D\;(4)A\rightarrow B\rightarrow C\rightarrow D$。
然后对于四种路径，我们都能固定一条边而在另一边中枚举点。比如在$AB$中枚举中点，每次就算出答案后更新，若不优于当前解，则有一定概率还是往该方向移动，至于移动的具体方向，我也不知道，所以就强行rand了（什么鬼？跳点完全随机，这样子都能A），每次都找中点，直到两个边界点特别接近（弄个exp）。
最后再强行退火100次，就好了（退火太玄学，反正AC就是正解）。
$\;\;\quad$欢迎来踩博客：[five20](https://www.cnblogs.com/five20/p/9317547.html)（蒟蒻写题解不易，转载请注明出处，万分感谢！）
### 代码：
```cpp
#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;
}
```