40pts 玄关求调
查看原帖
40pts 玄关求调
717476
Gaochenxi103_QWQ楼主2024/6/18 23:11
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
struct P{
	int x,y,z;
};
double dist(P a,P b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
} 
int fa[N],T,n,h,r;
bool near(P a,P b)
{
	return dist(a,b)<=2*r;
}
bool near_other(P a,P b)
{
	return dist(a,b)<=r;
}
bool cmp(P a,P b)
{
	
	double va=dist(a,P{a.x,a.y,h}),vb=dist(b,P{b.x,b.y,h});
	if(va==vb)
	{
		return va<=vb;
	}
	else
	{
		return va<vb; 
	} 
}
int find(int m)
{
	if(fa[m]==m)
	{
		return m;
	}
	else
	{
		return fa[m]=find(fa[m]);
	}
}
void merge(int a,int b)
{
	int f1=find(a),f2=find(b);
	if(f1==f2) return ;
	fa[f2]==f1;
	return ;
}
signed main() {
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
//	freopen("P3958_4.in","r",stdin);
//	freopen("P3958.out","w",stdout);
//	cout<<dist(P{70,27,88},P{70,100,88});
	P a[N];
	cin>>T;
	while(T--)
	{
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].y>>a[i].z;
		}
		for(int i=1;i<=n;i++) fa[i]=i;
		sort(1+a,1+a+n,cmp);
		if(!near_other(a[1],P{a[1].x,a[1].y,h}))
		{
			cout<<"No\n";
			continue;
		}
		bool op=false;
//		cout<<near(P{a[1].x,a[1].y,a[1].z});
//		for(int i=1;i<=n;i++)
//		{
//			cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<"\n";
//		}
		for(int i=2;i<=n;i++)
		{
			if(near(a[i-1],a[i]))
			{
				merge(i-1,i);
				if(near_other(a[i],P{a[i].x,a[i].y,0}))
				{
					cout<<"Yes\n";
					op=true;
					break;
				}
			}
			if(near_other(a[i],P{a[i].x,a[i].y,0}) and near_other(a[find(i)],P{a[find(i)].x,a[find(i)].y,h}))
			{
				cout<<"Yes\n";
				op=true;
				break;
			}
		}
		if(near_other(a[1],P{a[1].x,a[1].y,0}) and !op)
		{
			cout<<"Yes\n";
			op=true;
		}
		if(!op) cout<<"No\n";
	}
	return 0;
}

2024/6/18 23:11
加载中...