Submission #1555584

---

Source Code Expand

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

/*
thx
http://cf16-exhibition-final-open.contest.atcoder.jp/submissions/1005311
*/

struct City{//位置x,位置y,水量
	int x,y,a;
};
void solve(){
	int N;
	cin >> N;
	vector<City> cities(N);
	for(int i=0;i<N;++i){
		int x,y,a;
		cin >> x >> y >> a;
		//cities[i] = {x,y,a};
		cities[i].x = x;
		cities[i].y = y;
		cities[i].a = a;
	}
	//dist[i][j]:=i,j間の距離
	vector< vector<double> > dist(N,vector<double>(N));
	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			//ユークリッド距離
			//dist[i][j] = hypot(cities[i].x-cities[j].x, cities[i].y-cities[j].y);
			//Cityの中がint
			// 10^5*10^5 などでOVF
			/*dist[i][j] = (cities[i].x-cities[j].x)*(cities[i].x-cities[j].x)
				+(cities[i].y-cities[j].y)*(cities[i].y-cities[j].y);
			dist[i][j] = sqrt( dist[i][j] );
			*/
			double X = (cities[i].x-cities[j].x);
			double Y = (cities[i].y-cities[j].y);
			dist[i][j] = sqrt(X*X+Y*Y);
		}
	}
	
	//初期化
	vector<double> mstCost(1<<N,1e99);
	for(int i=0;i<N;++i){
		mstCost[1<<i] = 0;
	}

	/*
	集合Sを連結にするための最小コスト:最小全域木
	(MST:Minimum Spanning Tree)
	*/
	for(int S=1;S<(1<<N)-1;++S){
		double x = mstCost[S];
		for(int i=0;i<N;++i){
			if( (S >> i) & 1 ){//
				for(int j=0;j<N;++j){
					if( ~S >> j & 1){//
						mstCost[S|(1<<j)] = min(mstCost[S|(1<<j)],
							x + dist[i][j]);
					}
				}
			}
		}
	}

	/////
	/*
	ある部分集合Sで、水量の平均を最大化すると
	value[S]になる。かな？
	*/
	vector<double> value(1<<N,0);
	for(int S=1;S<(1<<N);++S){
		double sumA = 0;//Sに含まれる都市の水量
		int K = 0;//Sに含まれる都市の数
		for(int i=0;i<N;++i){
			if( (S>>i) & 1 ){
				sumA += cities[i].a;
				++K;
			}
		}
		value[S] = max(0.0, sumA - mstCost[S]) / K;
	}

	/////
	vector<double> dp(1<<N);
	dp[0] = 1e99;
	/*
	あるSのときSの部分集合は計算済み
	*/
	for(int S=1;S<(1<<N);++S){
		double x = 0;//dp[S]での最大値を入れる

		//Sを分割して、それぞれ最小値の最大値を見る
		for(int T = S; T> 0 ; (--T) &= S ){
			//T=0の場合,value[0]=0 => min(value[0],dp[S]) => 0
			//max(x,0) => x
			x = max(x, min(value[T],dp[S-T]) );
		}
		dp[S] = x;
	}
	double ans = dp.back();//dp[(1<<N)-1];//dp.back();
	cout << ans << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Submission Info

Judge Result