题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4744
二分答案，然后n^2判断两个点之间是否可以建边，用并查集维护一下就可以了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<bits/stdc++.h> #define maxn 1010 #define inf INT_MAX #define ll long long using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct point{ int x,y; }p[maxn]; int n; int fa[maxn]; inline void init(){ n=rd(); for(int i=1; i<=n; i++)p[i].x=rd(),p[i].y=rd(); } int getroot(int x){ if(!fa[x])return x; return fa[x]=getroot(fa[x]); } inline bool check(int mid){ int num=0; memset(fa,0,sizeof fa); for(int i=1; i<=n; i++){ for(int j=i+1; j<=n; j++){ if((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)<=mid){ int x=getroot(i); int y=getroot(j); if(x==y)continue; fa[x]=y; num++; } } } return num==n-1; } inline void work(){ int l=0,r=inf,ans=0; while(l<=r){ int mid=(ll)(l+r)/2; if(check(mid))r=mid-1,ans=mid; else l=mid+1; } printf("%d\n",ans); } int main(){ init(); work(); return 0; } |
