代码厌氧+WA90pts求助
查看原帖
代码厌氧+WA90pts求助
541313
hepp楼主2024/5/18 16:25
#include<bits/stdc++.h>
using namespace std;
const double xp=0.995;
const int inf=1e9,N=1e3+10;
int n,m,r;
int a[25],b[25],c[25];
int p[N],q[N],ans;
double xs,ys;
double len(double x,double y,double u,double v){return sqrt((x-u)*(x-u)+(y-v)*(y-v));}
int ak(double x,double y)
{
	double l=r,f;
	int as=0;
	for(int i=1;i<=n;i++)
	{
		f=len(a[i],b[i],x,y);
		if(f<c[i])return 0;
		l=min(l,f-c[i]);
	}
	for(int i=1;i<=m;i++)
		if(len(p[i],q[i],x,y)<=l)
			as++;
	return as;
}
int SA()
{
	double T=3000;
	double x=xs,y=ys;
	while(T>=1e-18)
	{
		double ansx=x+(rand()*2-RAND_MAX)*T,ansy=y+((rand()*2)-RAND_MAX)*T;
		int d=ak(ansx,ansy);
		if(d>ans)
			ans=d,xs=x=ansx,ys=y=ansy;
		else if(exp((d-ans)/T)/RAND_MAX>rand())
			x=ansx,y=ansy;
		T*=xp;
	}
}
int main()
{
	srand(1);
	scanf("%d%d%d",&n,&m,&r);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for(int i=1;i<=m;i++){scanf("%d%d",&p[i],&q[i]);xs+=p[i],ys+=q[i];}
	xs/=m,ys/=m;
	while((double)clock()/CLOCKS_PER_SEC<0.8)
		SA();
	printf("%d",ans);
	return 0;
}
2024/5/18 16:25
加载中...