在一个长方形框子里, 最多有 N(0≤N≤6) 个相异的点,
在其中任何一个点上放一个很小的油滴, 那么这个油滴会一直扩展, 直到接触到其他油滴或者框子的边界.
必须等一个油滴扩展完毕才能放置下一个油滴. 那么应该按照怎样的顺序在这 N 个点上放置油滴, 才能使放置完毕后所有油滴占据的总体积最大呢?
- (不同的油滴不会相互融合)
- #include<cstdio>
- #include<cstdlib>
- #include<cmath>
- #include<algorithm>
- #define dd double
- using namespace std;
- int n;
- dd x[2],y[2],xx[8],yy[8];
- dd ds[8],dis[8][8];
- dd ans,nw[8];
- bool vis[8];
- void dfs(int cnt,dd sum)
- {
- if(cnt==n)
- {
- ans=max(ans,sum);
- return ;
- }
- for(int i=1;i<=n;i++)
- {
- if(vis[i]) continue;
- vis[i]=true;
- dd r=ds[i];
- for(int j=1;j<=n;j++)
- {
- if(i==j) continue;
- if(vis[j]) r=min(r,max(dis[i][j]-nw[j],0.0));
- //else r=min(r,dis[i][j]);
- // 确实, 每个点之间的距离会钳制 r 的长度, 但是后面的点对前面的点没有关系, 前面的点可以直接覆盖掉他
- }
- nw[i]=r;
- dfs(cnt+1,sum+r*r*3.1415926);
- vis[i]=false;
- }
- }
- int main()
- {
- scanf("%d",&n);
- scanf("%lf%lf%lf%lf",&x[0],&y[0],&x[1],&y[1]);
- for(int i=1;i<=n;i++)
- scanf("%lf%lf",&xx[i],&yy[i]),
- ds[i]=min( min(abs(xx[i]-x[0]),abs(xx[i]-x[1])) , min(abs(yy[i]-y[0]),abs(yy[i]-y[1])) );
- for(int i=1;i<n;i++)
- for(int j=i+1;j<=n;j++)
- dis[i][j]=dis[j][i]=sqrt((xx[i]-xx[j])*(xx[i]-xx[j]) + (yy[i]-yy[j])*(yy[i]-yy[j]) );
- dfs(0,0.0);
- dd tot=(x[0]-x[1])*(y[0]-y[1]);
- if(tot<0) tot=-tot;
- ans=tot-ans;
- printf("%0.0lf\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3260446.html