问为何TLE,30pts
查看原帖
问为何TLE,30pts
534562
liheyang123楼主2024/10/18 09:08

rt,纯SA板子,写了半个小时输入输出优化,总共调了1h,TLE on #1 #2 #3 #4 #6 #9 #10 #11

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N=1010;
const ld BT=1000;
const ld ET=1e-8;
const ld CT=0.988;
ld px[N],py[N],pr[N];
ld ex[N],ey[N];

int n,m,r;
ld ansx,ansy;
int answ;

inline int inget(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-48;ch=getchar();}
	return s*f;
}

inline ld read(){
	ld t=inget();
	ld t2=0.0,p=0.1;
	char ch=getchar();
	while(ch>='0'&&ch<='9'&&p>1e-13){t2+=(ch-'0')*p;p*=0.1;ch=getchar();}
	return t+t2;
}

inline void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar((x%10)+'0');
	return;
	
}

ld getdis(ld x,ld y,ld tx,ld ty){
	ld a=x-tx,b=y-ty;
	return sqrtl((ld)((a*a)+(b*b)));
}

int gets(ld x,ld y){
	ld madis=r;
	int res=0;
	for(int i=1;i<=n;i++)madis=min(madis,getdis(x,y,px[i],py[i])-pr[i]);
	for(int i=1;i<=m;i++)if(madis>=getdis(x,y,ex[i],ey[i]))res++;
	return res;
}

void SA(){
	int s=0;
	for(ld T=BT;T>=ET;T*=CT){
		ld ex=ansx+(rand()*2-RAND_MAX)*T;
		ld ey=ansy+(rand()*2-RAND_MAX)*T;
		int ew=gets(ex,ey);
		int de=ew-s;
		if(de>0){ansx=ex,ansy=ey;answ=max(answ,ew);s=ew;}
		else if(exp(de/T)<=rand()/RAND_MAX)ansx=ex,ansy=ey,s=ew;
	}
}

int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	srand(time(0)); 
	srand(rand());
	n=inget(),m=inget(),r=inget();
	//cin>>n>>m>>r;
	for(int i=1;i<=n;i++){
		//cin>>px[i]>>py[i]>>pr[i];
		//px[i]=read(),py[i]=read(),pr[i]=read();
		px[i]=inget(),py[i]=inget(),pr[i]=inget();
	}
	for(int i=1;i<=m;i++){
		//cin>>ex[i]>>ey[i];
		//ex[i]=read(),ey[i]=read();
		ex[i]=inget(),ey[i]=inget();
		ansx+=ex[i];
		ansy+=ex[i];
	}
	ansx=ansx/(ld)m;
	ansy=ansy/(ld)m;
	answ=gets(ansx,ansy);
	while(clock()/CLOCKS_PER_SEC<0.85)SA();
	print(answ);
	return 0;
} 
2024/10/18 09:08
加载中...