#30分求调
  • 板块学术版
  • 楼主lys_99
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/13 19:36
  • 上次更新2024/3/13 19:50:35
查看原帖
#30分求调
1026187
lys_99楼主2024/3/13 19:36
#include<bits/stdc++.h>
using namespace std;
int n,x1,y11,x2,y2,x[9],y[9],vis[9],a[9],xx1,yy1,xx2,yy2;
double d[9][9],r[9],sum,msum=1000009;
void dfs(int xxx){
	if(xxx>n){
		sum=0;
		//cout<<endl<<endl;
		for(int q=1;q<=n;q++){
			int i=a[q];
			r[i]=min(min(abs(x[i]-xx2),abs(xx1-x[i])),min(abs(y[i]-yy2),abs(yy1-y[i])));
			//cout<<i<<":"<<endl;
			//cout<<r[i]<<" ";
			for(int k=q-1;k>=1;k--){
				int j=a[k];
				//cout<<j<<"::"<<endl;
				//cout<<d[i][j]<<" "<<r[j]<<" ";
				//cout<<d[i][j]-r[j]<<" ";
				r[i]=min(r[i],d[i][j]-r[j]);
				//cout<<r[i]<<" "<<endl;
				if(r[i]<0){
					r[i]=0;
				}
			}
			sum+=M_PI*r[i]*r[i];
			//cout<<endl<<"bb"<<sum<<endl;
		}
		if(sum<msum){
		//	cout<<"***"<<msum<<" "<<sum<<endl;
			msum=sum;
		}

		return ;
	}
	if(xxx<=n){
		for(int i=1;i<=n;i++){
			if(vis[i]!=1){
				a[xxx]=i;
			//	cout<<a[xxx]<<" ";
				vis[i]=1;
				dfs(xxx+1);
				vis[i]=0;
			}
		}
		
	}
}
int main(){
    cin>>n>>x1>>y11>>x2>>y2;
   // x1+=1000;
   // y11+=1000;
   // x2+=1000;
    //y2+=1000;
    yy1=max(y11,y2);
    yy2=min(y11,y2);
    xx2=max(x1,x2);
    xx1=min(x1,x2);
    
    for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			d[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			d[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		//	cout<<endl;
		//	cout<<d[i][j]<<endl;
		}
	}
	dfs(1);
//	cout<<endl<<" aa "<<yy1<<" "<<yy2<<" "<<xx2<<" "<<xx1<<endl;
//	cout<<abs(yy1-yy2)*abs(xx1-xx2)<<" "<<msum<<endl;
	cout<<abs(yy1-yy2)*abs(xx1-xx2)-round(msum);
	return 0;
}
2024/3/13 19:36
加载中...