存代码用的
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #define db double
- using namespace std;
- db a[100][3]={0},s,x,y,x1,yy;
- db r[1010],ans=0.0;
- int vis[1000101]={0},n;
- double dis(db xx,db yy,db xx1,db yy1){
- return sqrt((xx-xx1)*(xx-xx1)+(yy-yy1)*(yy-yy1));
- }
- double minn(int k){
- for(int i=1;i<=n;i++)
- if(i!=k&&vis[i]==1)
- if(r[i]>dis(a[i][1],a[i][2],a[k][1],a[k][2])) return 0;
- double dist=0;
- double ans=min(min(abs(a[k][1]-x),abs(a[k][1]-x1)),min(abs(a[k][2]-y),abs(a[k][2]-yy)));
- for(int i=1;i<=n;i++)
- if(i!=k&&vis[i]==1){
- dist=dis(a[i][1],a[i][2],a[k][1],a[k][2])-r[i];
- ans=min(ans,dist);
- }
- return ans;
- }
- void dfs(int x,db y){
- if(x==n){
- ans=max(y,ans);
- return;
- }
- for(int i=1;i<=n;i++){
- if(!vis[i]){
- vis[i]=1;
- db lala=minn(i);
- dfs(x+1,y+3.14*lala*lala);
- r[i]=0;
- vis[i]=0;
- }
- }
- }
- int main(){
- scanf("%d",&n);
- scanf("%lf%lf%lf%lf",&x,&y,&x1,&yy);
- s=abs(x-x1)*abs(y-yy);
- for(int i=1;i<=n;i++)
- scanf("%lf%lf",&a[i][1],&a[i][2]);
- dfs(0,0.0);
- printf("%0.0f",s-ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2762976.html