10369 - Arctic Network

// Básicamente, es hacer una búsqueda binaria sobre todas las posibles
// distancias D, y para cada una de estas distancias calcular la cantidad de
// componentes conexos que quedan luego de intentar hacer un MST
// y según esta cantidad y la cantidad de satélites disponibles, verificar
// si cierto D cumple o no

#include
#include
#include
#include
#include
#include
using namespace std;

int p[500],rank[500];

void make_set(int x){
    p[x]=x;
   rank[x]=0;
}
void link(int x,int y){
    if(rank[x]>rank[y])
        p[y]=x;
    else{
        p[x]=y;
        if(rank[x]==rank[y]){
            rank[y]++;
        }
    }
}
int find_set(int x){
    if(x!=p[x]){
        p[x]=find_set(p[x]);
    }
    return p[x];
}
void Union(int x,int y){
    link(find_set(x),find_set(y));
}


int S,P;
pair pp[500];
vector<pair<double,pair<int,int> > > edg;

bool cumple(double D){
  for(int i=0;i 
  int sz=edg.size();
  for(int i=0;i
   double w=edg[i].first;
   int u=edg[i].second.first;
   int v=edg[i].second.second;
   if(find_set(u)!=find_set(v)){
      if( w<D) Union(u,v);
      else break;
   }
  }
  set ss;
  for(int i=0;i  sz=ss.size();
  if(sz==1) return true;
  if(sz&lt;=S) return true;
  else return false;
}

double solve(){
 double izq=0;
 double der=1e10;
 while(fabs(der-izq)&gt;1e-05){
  double mid=(izq+der)/2;
  if(cumple(mid)) der=mid;
  else izq=mid;
 }
 return (izq+der)/2;
}

int main(){
 int N;
 cin&gt;&gt;N;
 for(int tt=0;tt
   cin&gt;&gt;S&gt;&gt;P;
  
   for(int i=0;i&gt;pp[i].first&gt;&gt;pp[i].second;
   edg.resize(0);
   for(int i=0;i     int dx=pp[i].first-pp[j].first;
     int dy=pp[i].second-pp[j].second;
     double d=sqrt(dx*dx+dy*dy);
    edg.push_back(make_pair(d,make_pair(i,j)));
   }
   sort(edg.begin(),edg.end());
   double ret=solve();
   printf("%.2lf\n",ret);
 }
}