Submission #1802118

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef double db;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pct __builtin_popcount

#define N 15

struct P {
  int x, y;
  P(){}
  P(int _x, int _y):x(_x), y(_y) {}
  P operator + (const P&a) const {return P(x+a.x, y+a.y);}
  P operator - (const P&a) const {return P(x-a.x, y-a.y);}
  ll dot (const P&a) const {return (ll)x*a.x + (ll)y*a.y;}
  ll crs (const P&a) const {return (ll)x*a.y - (ll)y*a.x;}
  db dis (const P&a) const {return sqrt((ll)(x-a.x)*(x-a.x) + (ll)(y-a.y)*(y-a.y));}
} a[N];

int n, c[N];
db f[1<<N];
db g[1<<N];

int fn[N];
int fa(int x) {
	if (x == fn[x]) return x;
	return fn[x] = fa(fn[x]);
}

bool cmp(PII x, PII y) {
	return a[x.fi].dis(a[x.se]) < a[y.fi].dis(a[y.se]);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i ++)
		cin >> a[i].x >> a[i].y >> c[i];
	for (int p = 1; p < (1<<n); p ++) {
		vector<PII> b;
		for (int i = 0; i < n; i ++)
			for (int j = i+1; j < n; j ++)
				if (((p>>i)&1) && ((p>>j)&1))
					b.pb(mp(i, j));
		sort(b.begin(), b.end(), cmp);
		for (int i = 0; i < n; i ++) fn[i] = i;
		db dd = 0;
		for (int i = 0; i < (int) b.size(); i ++)
			if (fa(b[i].fi) != fa(b[i].se)) {
				dd += a[b[i].fi].dis(a[b[i].se]);
				fn[fa(b[i].fi)] = fa(b[i].se);
			}
		for (int i = 0; i < n; i ++)
			if ((p>>i)&1) g[p] += c[i];
		(g[p] -= dd) /= pct(p);
	}
	memset(f, 0, sizeof f);
	f[0] = 1e10;
	for (int p = 0; p < (1<<n); p ++) {
		vector<int> b;
		for (int i = 0; i < n; i ++)
			if (~(p>>i)&1) b.pb(i);
		int bs = (int) b.size();
		for (int q = 1; q < (1<<bs); q ++) {
			int c = 0;
			for (int j = 0; j < bs; j ++)
				if ((q>>j)&1) c |= (1<<b[j]);
			f[p|c] = max(f[p|c], min(f[p], g[c]));
		}
	}
	printf ("%.9lf\n", f[(1<<n)-1]);
	return 0;
}

Submission Info

Judge Result