类模拟退火,求调,WA on #2
查看原帖
类模拟退火,求调,WA on #2
230243
syf2008楼主2022/8/24 10:55
#include <bits/stdc++.h>
using namespace std;
int ww,zf;char c;
int read()
{
	ww=0;zf=1;c=getchar();
	while(c<'0'||c>'9'){if(c=='-')zf=-1;c=getchar();}
	while(c>='0'&&c<='9'){ww=(ww<<3)+(ww<<1)+(c^48);c=getchar();}
	return ww*zf;
}
int n,m,sum,pre,now,maxn,shang=6500;
double x[12],y[12],r[12],xx[1005],yy[1005];
double rr,maxr,p1,p2,fu1,fu2,t,sum1,sum2;
double prex,prey,nowx,nowy;
mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
double dis(double x,double y,double xx,double yy){return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));}
int check(double xxx,double yyy)
{
	sum=0;maxr=rr;
	for(int i=1;i<=n;i++)
	maxr=min(maxr,dis(xxx,yyy,x[i],y[i])-r[i]);
	for(int i=1;i<=m;i++)
	if(dis(xxx,yyy,xx[i],yy[i])<=maxr)sum++;
	return sum;
}
signed main()
{
	n=read();m=read();rr=read();
	for(int i=1;i<=n;i++){x[i]=read();y[i]=read();r[i]=read();}
	for(int i=1;i<=m;i++){xx[i]=read();yy[i]=read();sum1+=xx[i];sum2+=yy[i];}
	while(clock()<CLOCKS_PER_SEC*0.98)
	{
		prex=sum1/m;prey=sum2/m;
		pre=check(prex,prey);
		if(pre>maxn)maxn=pre;
		t=1;
		for(int j=4600;j>=1;j--,t*=0.9961)
		{
			p1=rnd()%shang+1;fu1=rnd()&1?1:-1;
			p2=rnd()%shang+1;fu2=rnd()&1?1:-1;
			nowx=prex+p1*fu1*t;
			nowy=prey+p2*fu2*t;
			now=check(nowx,nowy);
			if(now>pre)
			{
				if(rnd()%j>rnd()%(j+13)){prex=nowx;prey=nowy;pre=now;}//有概率接受当前解
				if(now>maxn)maxn=now;
			}
		}
	}
	printf("%d",maxn);
	return 0;
}
2022/8/24 10:55
加载中...