成功达成成就：很有困意的情况下写完了一道搜索题，而且不是一遍写对，是后来又查了错。。
困的情况下也能写出这种稍微有些麻烦的搜索题足见我功力之高（逃
需要注意一下输出时会出现的精度问题，否则WA两个点。
参考：https://www.luogu.org/blog/2002102430204070yl/solution-p1378
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include<iostream> #include<algorithm> #include<cmath> using namespace std; int n; int x01,y01,x02,y02; struct point{ int x,y; double r; bool occupied; }points[10]; int arr[10]; double dis[10][10]; inline double dist(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } inline double checkR(int p){ if(points[p].occupied)return 0; double r=min(min(abs(y01-points[p].y),abs(y02-points[p].y)),min(abs(x01-points[p].x),abs(x02-points[p].x))); for(int i=1;i<=n;i++){ if(i==p||!points[i].occupied)continue; r=min(r,dis[p][i]-points[i].r); } if(r<0)r=0; points[p].r=r; points[p].occupied=true; for(int i=1;i<=n;i++){ if(points[i].occupied)continue; if(r>=dis[p][i])points[i].occupied=true; } return r*r*3.1415926; } inline double dfs(int pos,double area){ if(pos==n+1)return area; return dfs(pos+1,area+checkR(arr[pos])); } int main(){ cin>>n; cin>>x01>>y01>>x02>>y02; for(int i=1;i<=n;i++)cin>>points[i].x>>points[i].y; for(int i=1;i<=n;i++)arr[i]=i; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ double v=dist(points[i].x,points[i].y,points[j].x,points[j].y); dis[i][j]=dis[j][i]=v; } } double maxV=0; do{ for(int i=1;i<=n;i++){ points[i].r=0; points[i].occupied=false; } double v=dfs(1,0); maxV=max(maxV,v); }while(next_permutation(arr+1,arr+n+1)); long long v=(long long)(abs(x01-x02)*abs(y01-y02)-maxV+0.5); cout<<v; } |