正题

---

题目大意

有n个点，给出坐标，选择所有距离在k之内的边要求联通所有点，求最小的k。

---

解题思路

垃圾解法

用二分答案然后加并查集求是否联通。

时间复杂度：O(mlogn)O(mlogn)

正解

按距离排序，然后连边到所有岛都联通为止。

时间复杂度：O(mlogm)O(mlogm)

---

垃圾解法的代码

#include
    
     #include
     
      #include
      
       using namespace std;struct node{    int from,to;    double w;}a[1000001];int n,dx[1001],dy[1001],dr[1001],father[1001],s,tot;double dis(double x1,double y1,double x2,double y2){  return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}//求距离bool cmp(node xxx,node yxx)//排序{
   return xxx.w
      
     
    

---

对拍

数据生成

#include
    
     #include
     
      #include
      
       #define random(x) rand()*rand()%x+1using namespace std;int n,m;int main(){    freopen("air.in","w",stdout);    srand((unsigned)time(0));    n=random(1000);    //n=1000;    printf("%d\n",n);    for (int i=1;i<=n;i++)    {      printf("%d %d %d\n",random(1000),random(1000),random(5));    }}
      
     
    

判断加对拍

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int n,dx[1001],dy[1001],dr[1001],father[1001],s,l;bool ok;double dis(double x1,double y1,double x2,double y2){  return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}int find(int x){
   return father[x]==x?x:father[x]=find(father[x]);}void unionn(int x,int y){    int fa=find(x),fb=find(y);    if (fa==fb) return;    else    {        if (fa
        
         1000)          {
   printf("TLE");break;}        freopen("air.in","r",stdin);        scanf("%d",&n);        for (int i=1;i<=n;i++)          scanf("%d%d%d",&dx[i],&dy[i],&dr[i]);        fclose(stdin);        freopen("air.out","r",stdin);        scanf("%d",&l);        s=n;ok=false;        for (int i=1;i<=n;i++)          father[i]=i;        for (int i=1;i<=n;i++)        {          for (int j=1;j<=n;j++)          {            double lw=dis(dx[i],dy[i],dx[j],dy[j])-dr[i]-dr[j];            if (lw<=l)            {                unionn(i,j);            }            if (s==1) ok=true;          }          if (s==1) ok=true;        }        if (s!=1)        {
   printf("WA");break;}        fclose(stdin);        printf("AC point:%d time:0.%0.lf\n",ti,ed-st);    }}