题解：P13820 「LDOI R3」村村振兴

· · 题解

好题。

我们有一个朴素的模拟退火做法，但朴素做法计算点 (x,y) 对应的答案时复杂度是 O(n+m) 的，由于 n 很大，单次计算答案所耗时间就会很多，因此退火就没法跑很多次，每次跑的过程也一定不完全不充分。

考虑到 m 极小，那么就应考虑能否优化掉 n，它是单次计算的复杂度瓶颈。

有个显然的结论，你想计算某个点到一个点集中所有点的距离最大值，只需计算这个点到这个点集对应的凸包上的所有点的距离的最大值就行了。

那么回到这道题，将这 n 个点的凸包求出，每次只计算凸包上的点并取距离的最大值就行了。

然后随机了一组数据发现优化了特别多，观察了随机数据下凸包上的点的个数大概是 O(\log n) 级别的。

这个结论不会证，OI 种的很多量在随机数据下似乎都会退化成 \log，感觉很高妙但是做题又不用证明。

我们现在拥有了 O(\log n+m) 的单次复杂度，加在朴素退火的代码上是否就能通过了呢？

答案是不行，考虑一下这个题的特殊性，它的特殊性在于，某个坐标对应的答案函数 f(x,y) 并不处处连续，因此，我们的退火很容易困在一个地方出不来。

所以说我们考虑不断随机起始坐标，对于每一个起始坐标都跑一遍退火。

随机多少次呢？答案是能随机多少次就随多少次，可以用 C++ 自带的用时统计函数保证不超时。

这样就能过了，然而我赛时一个唐错没查出来，赛后删了一行就直接过了。

int main(){
    srand(time(0));
    cin>>n>>m;
    rep(i,1,n){
        cin>>a[i].x>>a[i].y;
        ansx+=a[i].x;
        ansy+=a[i].y;
        mxx=max(mxx,a[i].x);
        mxy=max(mxy,a[i].y);
    }
    ansx/=n;
    ansy/=n;
    sort(a+1,a+n+1,cmp);
    s[top=1]=1;
    rep(i,2,n){
        do{
            if(top<2) break;
            if(slope(s[top-1],s[top])>slope(s[top-1],i)) --top;
            else break;
        }while(1);
        s[++top]=i;
    }
    while(top>1){
        ans+=dis(s[top],s[top-1]);
        v.pb(s[top]);
        --top;
    }
    s[top=1]=n;
    repp(i,n-1,1){
        do{
            if(top<2) break;
            if(slope(s[top-1],s[top])>slope(s[top-1],i)) --top;
            else break;
        }while(1);
        s[++top]=i;
    }
    while(top>1){
        ans+=dis(s[top],s[top-1]);
        v.pb(s[top]);
        --top;
    }
    double Ans=inf;
    rep(i,1,m) cin>>xx[i]>>yy[i]>>r[i]>>c[i];
    while((double)clock() / CLOCKS_PER_SEC <= 0.95){
        ansx=((2*randnum())*1.0/RAND_MAX)*mxx;
        ansy=((2*randnum())*1.0/RAND_MAX)*mxy;
        ans=inf;
        rep(i,1,10) SA();
        Ans=min(Ans,ans);
    }
    printf("%.10lf",Ans);
    return 0;
}

如果您这么写完没过，欢迎找我要退火参数。