社区讨论

P1378 #1AC 其他全WA(有注释)

P1378油滴扩展参与者 4已保存回复 9

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@lo892u8x
此快照首次捕获于
2023/10/27 14:46
2 年前
此快照最后确认于
2023/10/27 14:46
2 年前
查看原帖
CPP
#include <iostream>
#include <cstring>
#include <cmath>
#define pi 3.1415926535897932384626433832795028841971
#define px p[i][0]
#define py p[i][1]
#define qx p[j][0]
#define qy p[j][1]
using namespace std;
double dis[10][10];
double p[10][2];
int n;
double mark[10];
double ans=-1;
double x_1,y_1,x_2,y_2;
void dfs(int now,int step){
	if(step==n){
		double res=0;
		for(register int i=1;i<=n;++i){
			res+=mark[i]*mark[i]*pi;
		}
		ans=max(ans,res);
		return ;
	}
	for(register int i=now+1;i<=n;++i){
		if(mark[i]!=-1)continue;//若点i来过,则忽略
		//找距i点最近的圆周
		double minn=2147483647000;
		for(register int j=1;j<=n;++j){
			if(j==i || mark[j]==-1)continue;
			double d=dis[i][j]-mark[j];
			if(d<=0){//i点已经被油滴包含
				minn=0;
				break;
			}
			minn=min(minn,d);
		}
		//找到距i点最近的边框
		double d=min(abs(x_1-px),abs(x_2-px));
		d=min(d,abs(y_1-py));
		d=min(d,abs(y_2-py));
		
		minn=min(minn,d);
		mark[i]=minn;
		dfs(i,step+1);
//		mark[i]=-1;
	}
}
int main(){
	cin>>n;
	cin>>x_1>>y_1>>x_2>>y_2;
	for(register int i=1;i<=n;++i){
		cin>>px>>py;
		mark[i]=-1;
	}
	for(register int i=1;i<=n;++i){
		for(register int j=i+1;j<=n;++j){
			dis[i][j]=dis[j][i]=sqrt((px-qx)*(px-qx)+(py-qy)*(py-qy));
		}
	}
	dfs(0,0);
	cout<<round(ans);
	return 0;
}

回复

9 条回复,欢迎继续交流。

正在加载回复...