E - Water Distribution
Time limit : 2sec / Memory limit : 256MB

Score : 1000 points

Problem Statement
There are N cities in a two-dimensional plane. The coordinates of the i-th city is (xi,yi). Initially, the amount of water stored in the i-th city is ai liters.

Snuke can carry any amount of water from a city to another city. However, water leaks out a bit while he carries it. If he carries l liters of water from the s-th city to the t-th city, only max(l−ds,t,0) liters of water remains when he arrives at the destination. Here ds,t denotes the (Euclidean) distance between the s-th city and the t-th city. He can perform arbitrary number of operations of this type.

Snuke wants to maximize the minimum amount of water among the N cities. Find the maximum X such that he can distribute at least X liters of water to each city.

Constraints
1≤N≤15
0≤xi,yi,ai≤109
All values in the input are integers.
No two cities are at the same position.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int M=20,N=(1<<15)+10;
double g[M][M],dis[M];
int vis[M],n,x[M],y[M],a[M];
double dp[N];
double dist(double x,double y) { return sqrt(x*x+y*y); }
double solve(vector<PII> x) {
    int m=SZ(x);
    rep(i,0,m) rep(j,i+1,m) g[i][j]=g[j][i]=dist(x[i].fi-x[j].fi,x[i].se-x[j].se);
    rep(i,0,m) vis[i]=0;
    vis[0]=1; rep(i,1,m) dis[i]=g[0][i];
    double r=0;
    rep(i,0,m-1) {
        double pd=1e20; int pp=-1;
        rep(j,0,m) if (!vis[j]&&dis[j]<pd) {
            pd=dis[j]; pp=j;
        }
        vis[pp]=1; r+=pd; 
        rep(j,0,m) dis[j]=min(dis[j],g[pp][j]);
    }
    return r;
}
int main() {
    scanf("%d",&n);
    rep(i,0,n) scanf("%d%d%d",x+i,y+i,a+i);
    rep(S,1,(1<<n)) {
        vector<PII> v;
        rep(i,0,n) if (S&(1<<i)) {
            dp[S]+=a[i];
            v.pb(mp(x[i],y[i]));
        }
        dp[S]-=solve(v); dp[S]/=SZ(v);
    }
    rep(S,1,(1<<n)) {
        int nS=S;
        while (1) {
            dp[S]=max(dp[S],min(dp[nS],dp[S-nS]));
            if (nS==0) break;
            nS=(nS-1)&S;
        }
    }
    printf("%.10f\n",dp[(1<<n)-1]);
}