萌新的求助——P1378 油滴扩展
  • 板块P1378 油滴扩展
  • 楼主夜明
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/7/27 09:29
  • 上次更新2023/11/6 22:09:15
查看原帖
萌新的求助——P1378 油滴扩展
305891
夜明楼主2020/7/27 09:29

60分,#2#4#7#9WA。

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int a[8][2],x[4],n;
const double pai=3.1415927;
double b[8][8],maxx;
bool g[8]; 
void search_dfs(int u,double sum){
	//cout<<u<<"-------->"<<sum<<endl;
	if(u>n){
		maxx=min(maxx,abs((x[0]-x[2])*(x[1]-x[3]))-pai*sum);
		return;
	}
	for(int i=1;i<=n;i++){
		if(g[i])continue;
		double hh=400055550;
		bool hhhhhhh=true;
		for(int j=0;j<=n;j++){
			if(b[i][j]<0&&i!=j&&j>0){
				hhhhhhh=false;
				return;
			}
			if(hhhhhhh&&!(!g[j]&&j>0)&&!(j==i))hh=min(hh,b[i][j]);
			//cout<<b[i][j]<<" ";
		}
		if(!hhhhhhh)continue;
		//cout<<endl;
		for(int j=0;j<=n;j++)b[i][j]-=hh;
		for(int j=1;j<=n;j++)b[j][i]-=hh;
		b[i][i]+=hh;
		g[i]=true;
		search_dfs(u+1,sum+hh*hh);
		for(int j=0;j<=n;j++)b[i][j]+=hh;
		for(int j=1;j<=n;j++)b[j][i]+=hh;
		b[i][i]-=hh;
		g[i]=false;
	}
}
int main(){
	memset(g,false,sizeof(g));
	cin>>n;
	for(int i=0;i<4;i++)cin>>x[i];
	maxx=int(abs((x[0]-x[2])*(x[1]-x[3])));
	//cout<<maxx;
	for(int i=1;i<=n;i++){
		cin>>a[i][0]>>a[i][1];
		double minx=400005550;
		for(int j=0;j<4;j++){
			if(j%2)minx=min(minx,sqrt((a[i][1]-x[j])*(a[i][1]-x[j])));
			else minx=min(minx,sqrt((a[i][0]-x[j])*(a[i][0]-x[j])));
		}
		b[0][i]=b[i][0]=minx;
		for(int j=1;j<i;j++){
			b[i][j]=b[j][i]=sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]));
		}
	}
	search_dfs(1,0);
	//cout<<maxx<<" ";
	if((maxx-floor(maxx))<0.5)cout<<int(maxx);
	else cout<<int(maxx)+1;
	return 0;
}
2020/7/27 09:29
加载中...