用的STL,为啥没过
查看原帖
用的STL,为啥没过
422996
HeCao2008楼主2023/2/12 22:40

蒟蒻的代码,变量名起的比较随意

#include<bits/stdc++.h>
using namespace std;
const int maxn=10;
int s[maxn]; 
struct node{
	double x,y;
}a[maxn];
double rrr[maxn];
int n,ans=2147483647,now;
double ll,rr,uu,dd,xx,yy,_xx,_yy,u,d,l,r,rec;
double dist(int aa,int b){
	return sqrt((a[aa].x-a[b].x)*(a[aa].x-a[b].x)+(a[aa].y-a[b].y)*(a[aa].y-a[b].y));
}
double dfs(){
	double rrrr=2147483647*1.0;
	double sum=0.0;
	for(int i=1;i<=n;i++){
		uu=u-a[i].y;
		dd=a[i].y-d;
		ll=a[i].x-l;
		rr=r-a[i].x;
		rrrr=2147483647*1.0;
		for(int j=1;j<i;j++)rrrr=min(rrrr,dist(i,j)-rrr[j]);
		if(rrrr<0){
			rrr[i]=0;
			continue;
		}
		rrr[i]=min(ll,min(rr,min(uu,min(dd,rrrr))));
		sum+=rrr[i]*rrr[i]*3.14159265358;
	}
	return sum;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	cin>>xx>>yy>>_xx>>_yy;
	l=min(xx,_xx),r=max(xx,_xx),u=max(yy,_yy),d=min(yy,_yy);
	for(int i=1;i<=n;i++)s[i]=i;
	for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	rec=(r-l)*(u-d);
	do{
	    now=(int)(round)(rec-dfs());
	    ans=min(ans,now);
	}while(next_permutation(s+1,s+n+1));
	cout<<ans<<"\n";
	return 0;
}

2023/2/12 22:40
加载中...