60分求助,知道自己这种方法有点...但想知道错在哪了
查看原帖
60分求助,知道自己这种方法有点...但想知道错在哪了
348820
Nekura_Yuki楼主2021/4/13 18:58
#include<bits/stdc++.h>
#include<string>
#define PI 3.1415926 
using namespace std;
typedef long long ll;
struct cir
{
	double x,y;double r;	
	cir(double xx,double yy,double rr)
	{
		x=xx,y=yy,r=rr;
	}
};
struct node
{
	double x,y;
}nodes[10];
double ans;
int n;
bool v[10];
double sx,sy,ex,ey;
double l,r,u,d;
int xu[10];
vector<cir> vec;
double dis(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void doit()
{
	memset(v,false,sizeof(v));
	vec.clear();
	for(int i=1;i<=n;i++)
	{
		int ind=xu[i];
		if(v[ind]) continue;
		int x=nodes[ind].x,y=nodes[ind].y;
		if(x<u||x>d||y<l||y>r) continue;
		double rd=y-l;
		rd=min(rd,r-y);
		rd=min(rd,x-u);
		rd=min(rd,d-x);
		if(!rd) continue;
		for(int j=0;j<vec.size();j++)
		{
			double cx=vec[j].x,cy=vec[j].y,cr=vec[j].r;
			rd=min(rd,dis(x,y,cx,cy)-cr);
		}
		double mind=rd;int mini=0;
		for(int j=i+1;j<=n;j++)
		{
			if(mind>=dis(x,y,nodes[xu[j]].x,nodes[xu[j]].y))
			{
				mind=dis(x,y,nodes[xu[j]].x,nodes[xu[j]].y);
				mini=j;
			}
		}
		rd=mind,v[mini]=true;
		if(rd)
		vec.push_back(cir(x,y,rd));
	}	
	double ss=0.0;
	for(int i=0;i<vec.size();i++)
	{
		ss+=PI*vec[i].r*vec[i].r;
	}
	ans=max(ans,ss);
}	
int main()
{	
	freopen("data.txt","r",stdin);
	cin>>n;
	cin>>sx>>sy>>ex>>ey;
	u=min(sx,ex);
	d=max(sx,ex);
	l=min(sy,ey);
	r=max(sy,ey);
	double ssum=(r-l)*(d-u);
	for(int i=1;i<=n;i++)
	{
		cin>>nodes[i].x>>nodes[i].y;
		xu[i]=i; 
	}
	do
	{
		doit();
	}while(next_permutation(xu+1,xu+1+n));
	cout<<fixed<<setprecision(0)<<ssum-ans;
	return 0;
}

 
2021/4/13 18:58
加载中...