Submission #1564394

---

Source Code Expand

#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
in p2(in a){
  return 1LL<<a;
}
struct unifnd{
  VI ht,pr;
  in fnd(in a){
    in ta=a;
    while(a!=pr[a])a=pr[a];
    in tt=ta;
    while(ta!=a){
      tt=pr[ta];
      pr[ta]=a;
      ta=tt;
    }
    return a;
  }
  void uni(in a, in b){
    a=fnd(a);
    b=fnd(b);
    if(a==b)return;
    if(ht[b]<ht[a])swap(a,b);
    pr[a]=b;
    ht[b]+=(ht[a]==ht[b]);
  }
  void ini(in n){
    ht.resize(n);
    pr.resize(n);
    forn(i,n){
      ht[i]=0;
      pr[i]=i;
    }
  }
};
unifnd tfd;
vector<double> x,y,a;
vector<double> bspan;
vector<pair<double,pair<in,in> > > egs;
double sq(double d){
  return d*d;
}
double dist(in i, in j){
  return sqrt(sq(x[i]-x[j])+sq(y[i]-y[j]));
}
vector<double> btot;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  x=y=a=vector<double>(n);
  forn(i,n){
    cin>>x[i]>>y[i]>>a[i];
  }
  forn(i,n){
    forn(j,i){
      egs.PB(MP(dist(i,j),MP(i,j)));
    }
  }
  sort(all(egs));
  bspan.resize(p2(n));
  bspan[0]=2e9;
  in ta,tb;
  forn(msk,p2(n)){
    if(!msk)
      continue;
    double tsm=0;
    in tcnt=0;
    tfd.ini(n);
    forn(i,n){
      if(msk&p2(i)){
	tsm+=a[i];
	++tcnt;
      }
    }
    for(auto& eg:egs){
      ta=eg.second.first;
      tb=eg.second.second;
      if((msk&p2(ta))&&(msk&p2(tb))){
	if(tfd.fnd(ta)!=tfd.fnd(tb)){
	  tfd.uni(ta,tb);
	  tsm-=eg.first;
	}
      }
    }
    bspan[msk]=max(0.0,tsm/tcnt);
  }
  btot.resize(p2(n));
  btot[0]=2e9;
  forn(msk,p2(n)){
    if(!msk)
      continue;
    for(in lmsk=msk;lmsk>0;lmsk=(lmsk-1)&msk){
      btot[msk]=max(btot[msk],min(btot[msk^lmsk],bspan[lmsk]));
    }
  }
  cout<<setprecision(15);
  cout<<btot[p2(n)-1]<<endl;
  return 0;
}

Submission Info

Judge Result