RT,一直60,第二个测试点输出 2813,不知道是哪里出来问题,感觉也不是精度的问题,请求谷内各位大佬的帮助!
原码如下:
#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);
}