列表

详情

NC25998. Battle of Balls

描述

Now that you have a ball of radius r, you want it to go from the bottom boundary of the map to the top boundary of the map (starting and ending points can be considered outside the map, entering the map from the bottom boundary and leaving the map from the top boundary). But there are a lot of little spikes in the map, and we can think of them as points. Your ball can't touch any of the points and the left or the right boundary of the map, even if the edge of the ball can't touch them. The area of the map can be seen as , with the lower left corner (0,0)and the upper right corner (100,100). The bottom boundary is y = 0, and the top boundary is y = 100.

输入描述

The first line contains an integer T, representing the number of data sets.
After that, there were T sets of data. In each set:
The first line contains an integer n ,which represents the number of small spikes, and a floating point number r, which is your ball's radius. 
The next n lines, each line containing two floating point numbers x,y, representing the coordinates of the spikes.
,  , ,

输出描述

For each set of input, if the ball can reach the top boundary of the map, output Yes ; Otherwise, output No.

示例1

输入: 

1
1 25.0
50.0 50.0

输出: 

No

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 75ms, 内存消耗: 504K, 提交时间: 2021-02-27 22:29:34 

#include<bits/stdc++.h>
#define eps 1e-8
using namespace std;
double x[1010],y[1010];
int fa[1002];
int find(int x){
	if(fa[x]==-1) return x;
	else{
		fa[x]=find(fa[x]);
		return fa[x];
	}
}
void Unin(int a,int b){
	int x=find(a);
	int y=find(b);
	if(x!=y) fa[x]=y;
}
double dis(int a,int b){
	double d=hypot(x[a]-x[b],y[a]-y[b]);
	return d;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		memset(fa,-1,sizeof(fa));
		int n;
		double r;
		cin>>n>>r;
		r*=2.0;
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i];
			if(x[i]-r<=0) Unin(0,i);
			if(100-x[i]-r<=0) Unin(i,n+1);
			
		}
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				if(dis(i,j)-r<=eps) Unin(i,j); 
			}
		}
		if(find(0)==find(n+1)) cout<<"No"<<endl;
		else cout<<"Yes"<<endl;
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 30ms, 内存消耗: 416K, 提交时间: 2022-10-19 10:32:00 

#include<bits/stdc++.h>
using namespace std;
int T,fa[1010],n;
double r,x[1010],y[1010];
int find(int x){
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
double efs=1e-8;
double dis(int i,int j){
    return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>r;r*=2.0;
		for(int i=0;i<=n+1;i++)fa[i]=i;
		for(int i=1;i<=n;i++){
			cin>>x[i]>>y[i];
			for(int j=1;j<i;j++){
				if(dis(i,j)-r*r<=efs)fa[find(j)]=find(i);
			}
			if(x[i]-r<=efs)fa[find(i)]=find(0);
			if(100.0-x[i]-r<=efs)fa[find(i)]=find(n+1);
		}
		if(find(0)==find(n+1))cout<<"No"<<endl;
		else cout<<"Yes"<<endl; 
	}
	return 0;
}

上一题

© 2025 nowcoder.com