Submission #2669353

---

Source Code Expand

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-13;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}
int x[110];
int y[110];
int p[110];
double g[20][20];
double t[1<<15];
double dp[1<<15];
int UF[20];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
pair<double,pair<int,int> > edge[400];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d%d",x+i,y+i,p+i);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			g[i][j]=sqrt((long long)(x[i]-x[j])*(x[i]-x[j])+(long long)(y[i]-y[j])*(y[i]-y[j]));
		}
	}
	for(int i=1;i<(1<<a);i++){
		double tmp=0;
		int cnt=0;
		for(int j=0;j<a;j++){
			if(i&(1<<j)){
				cnt++;
				tmp+=p[j];
			}
		}
		for(int j=0;j<a;j++){UF[j]=-1;}
		int sz=0;
		for(int j=0;j<a;j++){
			for(int k=j+1;k<a;k++){
				if(i&(1<<j)){
					if(i&(1<<k)){
						edge[sz++]=make_pair(g[j][k],make_pair(j,k));
					}
				}
			}
		}
		std::sort(edge,edge+sz);
		for(int j=0;j<sz;j++){
			if(FIND(edge[j].second.first)!=FIND(edge[j].second.second)){
				tmp-=edge[j].first;
				UNION(edge[j].second.first,edge[j].second.second);
			}
		}
		t[i]=tmp/cnt;
	}
	dp[0]=mod;
	for(int i=1;i<(1<<a);i++){
		int j=i;
		while(j){
			dp[i]=max(dp[i],min(dp[i-j],t[j]));
			j=((j-1)&i);
		}
	}
	printf("%.12f\n",dp[(1<<a)-1]);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:42:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int a;scanf("%d",&a);
                      ^
./Main.cpp:44:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",x+i,y+i,p+i);
                              ^

Judge Result