40分求调,不知为何卡在一个点死循环
查看原帖
40分求调,不知为何卡在一个点死循环
1060212
Saturation楼主2025/6/19 11:46
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=3e3;
const int M=3e6;
int n,T;
double H,r,a[N],b[N],c[N];
int qd[N],cnt;
bool flag;
int h[N],ne[N],e[N],idx;
bool st[M];
int in()
{
	int ans=0,ff=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())
	{
		if(c=='-')
		{
			ff*=-1;
		}
	}
	for(;isdigit(c);c=getchar())
	{
		ans=ans*10+c-'0';
	}
	return ans*ff;
}
void out(int x)
{
	if(x<0)
	{
		x=-x;
		putchar('-');
	}
	if(x>=10)
	{
		out(x/10);
	}
	putchar(x%10+'0');
}
void add(int x,int y)
{
	e[++idx]=y;
	ne[idx]=h[x];
	h[x]=idx;
}
void dfs(int x)
{
	if(st[x])
	{
		return;
	}
	st[x]=1;
	if(abs(H-c[x])<=r)
	{
		flag=1;
		return;
	}
	for(int i=h[x];~i;i=ne[i])
	{
		int y=e[i];
		dfs(y);	
		
//		int ju=x*2000+y;
		
//		if(!st[ju])
//		{
//			st[ju]=1;
//			dfs(y);
//		}
	}
}
signed main()
{
//	freopen("P3958_5.in","r",stdin);
	T=in();
	while(T--)
	{
		n=in();
		H=in();
		cin>>r;
		memset(h,-1,sizeof h);
		memset(e,0,sizeof e);
		memset(ne,0,sizeof ne);
		memset(a,0,sizeof a);
		memset(b,0,sizeof b);
		memset(c,0,sizeof c);
		memset(qd,0,sizeof qd);
		memset(st,0,sizeof st);
		idx=0;
		cnt=0;
		for(int i=1;i<=n;i++)
		{
			a[i]=in();
			b[i]=in();
			c[i]=in();
			if(abs(c[i])<=r)
			{
				qd[++cnt]=i;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				double d=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])+(c[i]-c[j])*(c[i]-c[j]));
				if(d<=2*r)
				{
					add(i,j);
					add(j,i);
				}
			}
		}
		flag=0;
		for(int i=1;i<=cnt;i++)
		{
			dfs(qd[i]);
			if(flag)
			{
				break;
			}
		}
		if(flag)
		{
			cout<<"Yes"<<endl;
		}
		else
		{
			cout<<"No"<<endl;
		}
	}
	return 0;
}
2025/6/19 11:46
加载中...