求助,蒟蒻60了三回啊三回
  • 板块P1378 油滴扩展
  • 楼主PCCP
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/5/12 19:43
  • 上次更新2023/10/23 16:00:20
查看原帖
求助,蒟蒻60了三回啊三回
310773
PCCP楼主2023/5/12 19:43

RT,一直60,第二个测试点输出 28132813,不知道是哪里出来问题,感觉也不是精度的问题,请求谷内各位大佬的帮助!

原码如下:

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef pair<double,double> PDD;
const int N=10;
int n;
double dist[N][N],rad[N],res,X1,Y1,X2,Y2;
bool st[N];
PDD pos[N];
void dfs(int step,double sum){
	if(step==n){
		res=max(res,sum);
		return;
	}
	for(int i=1;i<=n;i++){
		if(st[i]){
			continue;
		}
		double r=dist[i][0];
		bool flag=true;
		for(int j=1;j<=n;j++){
			if(st[j]&&j!=i){
				if(dist[i][j]-rad[j]<=0){
					flag=false;
				}
				r=min(r,dist[i][j]-rad[j]);
			}
		}
		if(flag==false){
			continue;
		}
		st[i]=true;
		rad[i]=r;
		dfs(step+1,sum+r*r);
		rad[i]=0;
		st[i]=false;
	}
}
int main(){
	scanf("%d%lf%lf%lf%lf",&n,&X1,&Y1,&X2,&Y2);
	X1+=1000;
	X2+=1000;
	Y1+=1000;
	Y2+=1000;
	if(X1>X2){
		swap(X1,X2);
	}
	if(Y1>Y2){
		swap(Y1,Y2);
	}
	for(int i=1;i<=n;i++){
//	cout<<"scheiBe"<<endl;
		scanf("%lf%lf",&pos[i].first,&pos[i].second);
		pos[i].first+=1000;
		pos[i].second+=1000;
		double x=min(abs(pos[i].first-X1),abs(pos[i].first-X2));
		double y=min(abs(pos[i].second-Y1),abs(pos[i].second-Y2));
		
		dist[i][0]=min(x,y);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dist[i][j]=sqrt((pos[i].first-pos[j].first)*(pos[i].first-pos[j].first)+(pos[i].second-pos[j].second)*(pos[i].second-pos[j].second));
		}
	}
	dfs(0,0);
	res*=3.1415926;
	res=(X2-X1)*(Y2-Y1)-res;
	printf("%.0lf\n",res);
}
2023/5/12 19:43
加载中...