题解 P2600 【[ZJOI2008]瞭望塔】

· · 题解

Po姐写了退火

TA博客访问量太高，然后又有布布扣这些东西

于是这道题搜出来一版的退火

我竟然信了

为了不辜负我四个小时的调参，我写份题解：

如果我们确定了横坐标，那么纵坐标可以二分出来

要求所有的折点与（xx，yy）的连线要是顺时针的，所以就是xx左边的点连向他左边斜率递增，右边也递增

然后高度与关于x是一个有峰的函数（为什么我不觉得是单峰）

所以可以退火来找横坐标！

最最重要的Tip：

这种计算几何用退火做而且精度要求不低的，退完火之后要在答案附近Rand上个千把次才是对的（之前没有加只有10分）

类似的这种题还有[JSOI2004]平衡点 / 吊打XXX、[POJ]Run Away，都是要在退火之后的答案附近找更优解的

#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