社区讨论
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 条回复,欢迎继续交流。
正在加载回复...