悬2关—40分求调
查看原帖
悬2关—40分求调
750476
Hf_Poem楼主2024/11/7 19:26
#include<bits/stdc++.h>
#define IXcape cout<<endl;return 0
#define Venti cout<<"\nVenti!\n"
using namespace std;
const int V=10;
const double pi=3.1415926535;
int n;
bool vis[V];
double ans=0,dis[V][V];
struct Point{
	int x,y;
	double r;
}st,en,ad[V];

inline
void init(void){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			dis[i][j]=sqrt(pow(ad[i].x-ad[j].x,2)+pow(ad[i].y-ad[j].y,2));
		}
	}
}

inline
void getx(){
	double s0=abs(st.x-en.x)*abs(st.y-en.y);
	for(int i=1;i<=n;i++){
		s0-=ad[i].r*ad[i].r*pi;
	}
		
	ans=min(ans,s0);
}

void dfs(int now){
	double dist=0x3f3f3f3f,flag=0;
	vis[now]=1;
	
	dist=min(double(abs(ad[now].x-st.x)),dist);
	dist=min(double(abs(ad[now].y-st.y)),dist);
	dist=min(double(abs(ad[now].x-en.x)),dist);
	dist=min(double(abs(ad[now].y-en.y)),dist);
	for(int i=1;i<=n;i++){
		if(i==now||ad[i].r==0) continue;
		if(ad[i].r>=dis[now][i]){
			ad[now].r=0;
			dfs(now+1);
		}
		dist=min(dist,(dis[now][i]-ad[i].r));
	}ad[now].r=dist;
	
	for(int i=1;i<=n;i++){
		if(vis[i]==0) flag=1;
	}
	if(flag==0){
		getx();
		return;
	}
	
	for(int i=1;i<=n;i++){
		if(i==now||vis[i]==1) continue;
		dfs(i);
		vis[i]=0;
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	cin>>st.x>>st.y>>en.x>>en.y;
	for(int i=1;i<=n;i++){
		cin>>ad[i].x>>ad[i].y;
	}init();
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof vis);
		dfs(i);
	}
	cout<<fixed<<setprecision(0)<<ans;
	IXcape;
}
/*

*/

球球辣(倒)

讲个笑话,如果把第32行的取min改成取max会多过一个点(什)

2024/11/7 19:26
加载中...