70求解(WA)
查看原帖
70求解(WA)
356003
Moeebius楼主2021/9/17 18:24
#include<bits/stdc++.h>
using namespace std;
int t;
long long n,h,r;
struct node{
	long long x,y,z;
};
node a[1001];

int f[1001];
int find(int x)
{
	return x==f[x] ? f[x] : f[x]=find(f[x]);
} 

bool check(int i, int j)
{
	//cout<<"check "<<i<<' '<<j<<endl;
	long double x=((double)a[i].x-(double)a[j].x)*((double)a[i].x-(double)a[j].x)+((double)a[i].y-(double)a[j].y)*((double)a[i].y-(double)a[j].y)+((double)a[i].z-(double)a[j].z)*((double)a[i].z-(double)a[j].z);
	return x<=(double)2*r*(double)2*r;
}

vector<int> kkk,sss;

void cal()
{
	for(int i=1; i<=n; i++){
		if(a[i].z<=r)
		{
			kkk.push_back(i);
		}
		else if(a[i].z>=n-r)
		{
			sss.push_back(i);
		}
		for(int j=i+1; j<=n; j++)
			if(check(i,j))
				f[find(i)]=find(j);
	}
}
void init(){
	for(int i=0; i<=1000; i++)
		f[i]=i;
}
long long miz[1001],maz[1001];
vector<int> idx;
void output()
{
	// memset(miz,-1,sizeof(miz));
	// memset(maz,-1,sizeof(maz));
	// for(int i=1; i<=n; i++)
	// {
	// 	if(miz[f[i]]==-1)
	// 	{
	// 		idx.push_back(f[i]);
	// 		miz[f[i]]=a[i].z;
	// 	}
	// 	miz[f[i]]=min(miz[f[i]],a[i].z);
	// 	maz[f[i]]=max(maz[f[i]],a[i].z);
	// }
	// for (std::vector<int>::iterator i = idx.begin(); i != idx.end(); ++i)
	// {
	// 	if(miz[*i]==-1||maz[*i]==-1) continue;
	// 	if(miz[*i]-r<=0 && maz[*i]+r>=h)
	// 	{
	// 		cout<<"Yes\n";
	// 		return;
	// 	}
	// }
	// cout<<"No\n";
	for(int i=0; i<kkk.size(); i++)
	{
		for(int j=0; j<sss.size(); j++)
		{
			if(find(kkk[i])==find(sss[j]))
			{
				cout<<"Yes\n";
				return;
			}
		}
	}
	cout<<"No\n";
}

int main(){
	cin>>t;
	while(t--)
	{
		memset(a,0,sizeof(a));
		init();
		cin>>n>>h>>r;
		for(int i=1; i<=n; i++)
		{
			scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);
		}
		cal();
		output();
	}
	return 0;
}
2021/9/17 18:24
加载中...