站外题求助
  • 板块学术版
  • 楼主louding
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/8/13 18:47
  • 上次更新2023/10/27 15:34:40
查看原帖
站外题求助
520626
louding楼主2022/8/13 18:47

在 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";

}
}

请大佬们帮我看看哪里错了,谢谢!

2022/8/13 18:47
加载中...