Submission #3518979

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;
 
template<typename tp> inline void read(tp &x) {
  x = 0; char c = getchar(); int f = 0;
  for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
  if (f) x = -x;
}
#define sqr(x) ((x) * (x))
#define db double
const int N = 16;
const int ST = 1 << (N + 1);
db x[N], y[N], a[N], d[N][N];
db sum[ST], dp[ST], f[ST];
int n;

int main(void) {
  cin >> n;
  re0 (i, n) {
    cin >> x[i] >> y[i] >> a[i];
  }
  int all = 1 << n;
  re0 (st, all) re0 (i, n) if (st >> i & 1) sum[st] += a[i];
  re0 (i, n) re0 (j, n)
    d[i][j] = sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
  fill(dp, dp + all, 1e18);
  re0 (st, all) {
    if (__builtin_popcount(st) <= 1) dp[st] =0;
    re0 (i, n) re0 (j, n)
    if (st >> i & 1 && !(st >> j & 1))
      dp[st | 1 << j] = min(dp[st | 1 << j], dp[st] + d[i][j]);
  }
  // re0 (st, all) cout << sum[st] << " "; cout << "\n";
  // re0 (st, all) cout << dp[st] << " "; cout << "\n";
  re0 (st, all) {
    f[st] = (sum[st] - dp[st]) / __builtin_popcount(st);
    for (int S = st; S; S = (S - 1) & st)
      f[st] = max(f[st], min(f[S], f[S ^ st]));
  }
  printf("%.10f\n", f[all - 1]);
}

Submission Info

Judge Result