Submission #58465060

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
const int N=10;
double n,s,t;
double a[N],b[N],c[N],d[N];
int op[N];
int opt[N];
double sum=0;
double dis(double x,double y,double xx,double yy){
  return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
}
double min1=1e9;
void solve(){
  double ans=sum;
  double sum2=0;
//  cout<<"____________________"<<endl;
  for(int i=1;i<=n;++i){
    int id1=op[i-1];
    int id2=op[i];
    double x,y,xx,yy; 
    if(opt[id1]==1){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
const int N=10;
double n,s,t;
double a[N],b[N],c[N],d[N];
int op[N];
int opt[N];
double sum=0;
double dis(double x,double y,double xx,double yy){
	return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
}
double min1=1e9;
void solve(){
	double ans=sum;
	double sum2=0;
//	cout<<"____________________"<<endl;
	for(int i=1;i<=n;++i){
		int id1=op[i-1];
		int id2=op[i];
		double x,y,xx,yy;	
		if(opt[id1]==1){
			x=a[id1];y=b[id1];
		}
		else{
			x=c[id1];y=d[id1];
		}
		if(opt[id2]==0){
			xx=a[id2];yy=b[id2];
		}
		else{
			xx=c[id2];yy=d[id2];
		}
//		cout<<id2<<" "<<op[id2]<<end;
//		cout<<id1<<" "<<id2<<endl;
//		cout<<x<<" "<<y<<" "<<xx<<" "<<yy<<endl;
		sum2+=dis(x,y,xx,yy); 
//		cout<<dis(x,y,xx,yy)<<endl;
//		cout<<sum2<<endl;	
	}
	
	sum2/=s;
	
//	if(!(op[1]==2 and op[2]==1 and op[3]==3))return ; 
//	for(int i=1;i<=n;++i){
//		cout<<op[i]<<" ";
//	}
//	cout<<endl;
//	for(int i=1;i<=n;++i){
//		cout<<opt[i]<<" ";
//	}
//	cout<<endl;
//	cout<<sum2<<endl;
	ans+=sum2;//if(ans<=9200)cout<<sum2<<endl;
	min1=min(min1,ans);
//	if(min1<=9200){
//		for(int i=1;i<=n;++i){
//		cout<<op[i]<<" ";
//	}
//	cout<<endl;
//	for(int i=1;i<=n;++i){
//		cout<<opt[i]<<" ";
//	}	
//	cout<<endl;
//	cout<<sum2<<" "<<ans<<endl;
//	exit(0);
//	}
}
void dfs(int step){
	if(step==n){
		solve();
		return ;
	}
	opt[step+1]=0;
	dfs(step+1);
	opt[step+1]=1;
	dfs(step+1); 
}
int main(){
	cin>>n>>s>>t;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		sum+=dis(a[i],b[i],c[i],d[i]);
	}
	sum/=t;
//	cout<<sum<<endl;
	for(int i=1;i<=n;++i){
		op[i]=i;
	}
	do{
		dfs(0);
	}
	while(next_permutation(op+1,op+(int)n+1));
	printf("%.12lf",min1);
} 

Submission Info

Judge Result