2019ACM河北省省赛——Battle of Balls

河北省省赛——Battle of Balls"/>

2019ACM河北省省赛——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 100 \times 100100×100, 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.
1001≤T≤100, 0 ≤n≤1000 , 0 ≤r≤1000, 0≤x,y≤100
输出描述:
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

思路
借鉴大佬
并查集，看的别人的
这个做法是有尖刺的地方若距离小于r，那么将其连通起来。
判断距离是否小于r 的时候要注意比较的数据是double
这题整了半天然后，然后一直示测试样例通过0%，一行一行找错发现把数组fa[1001],改成fa[1002]就对了。
代码

#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 merge(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) merge(0,i);if(100-x[i]-r<=0) merge(i,n+1);}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(dis(i,j)-r<=eps) merge(i,j); }}if(find(0)==find(n+1)) cout<<"No"<<endl;else cout<<"Yes"<<endl;}return 0;
}