题解 P2600 【[ZJOI2008]瞭望塔】

### Po姐写了退火 ### TA博客访问量太高，然后又有布布扣这些东西 ### 于是这道题搜出来一版的退火 ### 我竟然信了 为了不辜负我四个小时的调参，我写份题解： 如果我们确定了横坐标，那么纵坐标可以二分出来 要求所有的折点与（xx，yy）的连线要是顺时针的，所以就是xx左边的点连向他左边斜率递增，右边也递增 然后高度与关于x是一个有峰的函数（~~为什么我不觉得是单峰~~） 所以可以退火来找横坐标！ ### 最最重要的Tip： 这种计算几何用退火做而且精度要求不低的，退完火之后要在答案附近Rand上个千把次才是对的（~~之前没有加只有10分~~） 类似的这种题还有[JSOI2004]平衡点 / 吊打XXX、[POJ]Run Away，都是要在退火之后的答案附近找更优解的 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #define double long double using namespace std; const int N=400; int n,x[N],y[N]; double ans=1e15,lst,pos; int Check(double xx,double yy) { double lst=-1e15; int i; for(i=1;i<=n&&x[i]<xx;i++) { double a=1.0*(yy-y[i])/(xx-x[i]); if(a<lst) return 0; lst=a; } if(x[i]==xx) i++; lst=-1e15; for(;i<=n;i++) { double a=1.0*(yy-y[i])/(xx-x[i]); if(a<lst) return 0; lst=a; } return 1; } double Calc(double xx) { double l=0,r=1e11,res=1e12; while(r-l>1e-4) { double mid=(l+r)/2; if(Check(xx,mid)) r=mid,res=mid; else l=mid; } return res; } double Find(double xx) { for(int i=1;i<=n;i++) if(x[i]<xx&&x[i+1]>xx&&i!=n) return 1.0*(y[i+1]-y[i])/(x[i+1]-x[i])*(xx-x[i])+y[i]; else if(x[i]==xx) return y[i]; return 0; } double Rand(double l,double r) { double d=rand()%1000/1000.0; return d*(r-l)+l; } void SA(double T) { double y; for(;T>1e-5;T*=0.99) { double d=Rand(-1,1)*T; if(pos+d>x[n]||pos+d<x[1]) continue; y=Find(pos+d); double h=Calc(pos+d)-y; if(h<lst||exp((lst-h)/T)>Rand(0,1)) { ans=fmin(ans,h); pos=pos+d;lst=h; } } for(int i=1;i<=1000;i++) { double d=T*Rand(-1,1); if(pos+d>x[n]||pos+d<x[1]) continue; y=Find(pos+d); double h=Calc(pos+d)-y; lst=h;ans=fmin(ans,lst); } } int main() { srand(170530233); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&x[i]); for(int i=1;i<=n;i++) scanf("%d",&y[i]); for(int t=1;t<=5;t++) { int p=rand()%n+1; pos=x[p]; lst=Calc(pos)-y[p]; ans=fmin(ans,lst); SA(x[n]-x[1]); } if(ans<0) ans=0; printf("%.3Lf\n",ans); } ``` ~~轻轻松松倒数Rk1~~