在 x,y 坐标平面上给你 N 个圆,分别编号为 i=1,2,…,N。第 i个圆是以 (xi,yi) 为圆心, ri 为半径。
现在有两个点 (sx,sy) 和 (tx,ty) 在某些个圆的圆周上,问这两个点能否通过圆弧相互连通?
输入格式
第一行一个整数 T,表示数据的组数。
对于每组数据:
输入第一行,一个整数 N,表示圆的数量。
第二行输入四个以空格隔开的整数 sx,sy,tx,ty,为圆上的两个点。
接下来 N 行,每行输入三个以空格隔开的整数 xi,yi,ri 表示第 i 个圆的圆心和半径。
输出格式
输出共 T 行,如果 (sx,sy) 和(tx,ty) 能够通过圆弧相互连通,则输出 Yes,否则输出 No。
数据范围
对于100% 的数据, 1≤T≤10,1≤N≤3000,−109≤xi,yi≤109,1≤ri≤109。保证 (sx,sy) 和 (tx,ty) 均在某个圆的圆周上,且保证所有出现的数均为整数。
输出时每行末尾的多余空格,不影响答案正确性
要求使用「文件输入输出」的方式解题,输入文件为 circle.in,输出文件为 circle.out
样例输入
2
4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3
3
0 1 0 3
0 0 1
0 0 2
0 0 3
样例输出
Yes
No
样例2见剪贴板 https://www.luogu.com.cn/paste/ygsvmbq5
我的代码:
#include<bits/stdc++.h>
using namespace std;
long long n,t,sx,sy,tx,ty;
struct str{
long long x,y,r;
}a[10240];
bool con[3600][3600];
long long fa[10240];
double dis(long long xa,long long ya,long long xb,long long yb)
{
return sqrt((long long)(xa-xb)*(xa-xb)+(long long)(ya-yb)*(ya-yb));
}
long long circle(long long x,long long y)
{
for(long long i=1;i<=n;++i)
{
double d=dis(x,y,a[i].x,a[i].y);
if(d-a[i].r<0.000000001)
return i;
}
return -1;
}
bool connect(long long i,long long j)
{
double d=dis(a[i].x,a[i].y,a[j].x,a[j].y);
if(d>a[i].r+a[j].r||d<abs(a[i].r-a[j].r))
return 0;
return 1;
}
void init() {
for (long long i = 1; i <= n; i++) {
fa[i] = i;
}
}
long long get(long long x) {
if (fa[x] == x) {
return fa[x];
}
//return get(fa[x]); 这是修改前的操作
fa[x] = get(fa[x]); //路径压缩
return fa[x];
}
void merge(long long x, long long y) {
x = get(x);
y = get(y);
if (x != y) { // 不在同一个集合
fa[y] = x;
}
}
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
long long T;cin>>T;
while(T--){
init();
cin>>n;
cin>>sx>>sy>>tx>>ty;
for(long long i=1;i<=n;++i)
{
cin>>a[i].x>>a[i].y>>a[i].r;
}
long long s=circle(sx,sy),t=circle(tx,ty);
for(long long i=1;i<=n;++i)
for(long long j=1;j<=n;++j)
{
if(connect(i,j))
merge(i,j);
}
if(get(s)==get(t))
cout<<"Yes\n";
else
cout<<"No\n";
}
}
请大佬们帮我看看哪里错了,谢谢!