题解P5544

Chanter · 2020-07-29 21:42:22 · 题解

暴力是一种优雅

如果你还不会模拟退火，请看这里

这题要求的是最大值，所以要把else if(exp(-Delta/t)*RAND_MAX>rand())

改成else if(exp(-Delta/t)*RAND_MAX<rand())

另：一个有用的技巧 （O2）

while((double)clock()/CLOCKS_PER_SEC<=0.8) SA();

卡着时间调参的快乐（

上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _for(i,a,b) for(register int (i)=(a);(i)<=(b);(i)++)
#define For(i,a,b) for(register int (i)=(a);(i)>=(b);(i)--)
#define INF 0x7fffffff
#define il inline
#define rg register
inline long long read(){
    long long num=0;int z=1;char c=getchar();
    if(c=='-') z=-1;
    while((c<'0'||c>'9')&&c!='-') c=getchar();
    if(c=='-') z=-1,c=getchar();
    while(c>='0'&&c<='9') num=(num<<1)+(num<<3)+(c^48),c=getchar();
    return z*num;
}
il double Fread(){
    char c=getchar();int flag=1;double ans=0;
    while((!(c>='0'&&c<='9'))&&c!='-') c=getchar();
    if(c=='-') flag=-1,c=getchar();
    while(c>='0'&&c<='9') ans=ans*10+(c^48),c=getchar();
    if(c=='.'){c=getchar();for(rg int Bit=10;c>='0'&&c<='9';Bit=(Bit<<3)+(Bit<<1)) ans+=(double)(c^48)*1.0/Bit,c=getchar();}
    return ans*flag;
}
#define delta 0.9976
const int maxn=5e3+5;
class node{
    public:
        double x,y;
}p[maxn],q[maxn];
double r1[maxn];
int n,m;
double ansx,ansy,ax,ay,ans,t,r;
il void clear(){
    ax=ay=0;ans=1e8;
    return ;
}
il double cnt(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
il int calculate(double x,double y){
    int tot=0;
    double k=r;
    _for(i,1,n) k=min(k,cnt(x,y,p[i].x,p[i].y)-r1[i]);
    _for(i,1,m) if(cnt(x,y,q[i].x,q[i].y)<=k) tot++;
    return tot;
}
il void SA(){
    double x=ansx,y=ansy;
    t=20060.404;
    while(t>1e-18){
        double X=x+((rand()<<1)-RAND_MAX)*t,Y=y+((rand()<<1)-RAND_MAX)*t,now=calculate(X,Y),Delta=now-ans;
        if(Delta>0) ansx=X,ansy=Y,x=X,y=Y,ans=now;
        else if(exp(-Delta/t)*RAND_MAX<rand()) x=X,y=Y;
        t*=delta;
    }
    return ;
}
il void work(){
    ansx=ax/m,ansy=ay/m;
    while((double)clock()/CLOCKS_PER_SEC<=0.8)  SA();
    return ;
}
int main(){
    srand(114514);
    n=read(),m=read(),r=Fread();
    _for(i,1,n) p[i].x=Fread(),p[i].y=Fread(),r1[i]=Fread();
    _for(i,1,m) q[i].x=Fread(),q[i].y=Fread(),ax+=q[i].x,ay+=q[i].y;
    work();
    cout<<round(ans)<<'\n';
    return 0;
}