如果一个矩形 $A$ 包含另一个矩形 $B$, 那么选矩形 $A$ 显然不优.
把坐标离散化, 给每个矩形一个随机的 unsigned long long 权值, 并把对应范围内每个格子的权值都异或上它. Floodfill 找出所有权值相同的四连通格子, 如果某个连通块的形状是矩形, 那么就是一个可行的矩形, 一共 $O(n^2)$ 个.
为了让面积和最小, 将这些矩形按照面积从小到大排序, 依次用匈牙利算法匹配输入的 $n$ 个矩形即可, 可以用位运算加速匹配的过程.
时间复杂度 $O(\frac{n^4}{32})$.
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- typedef unsigned long long ull;
- typedef unsigned int U;
- const int N=70,inf=100000;
- int n,m,i,j,ca,cb,a[N],b[N];ull w[N],col[N][N],goal;
- int xl,xr,yl,yr,area,f[N],cnt,ans;
- bool vis[N][N];
- U g[N*N],v;
- struct Rect{
- int x1,y1,x2,y2,area;
- Rect(){}
- Rect(int _x1,int _y1,int _x2,int _y2,int _area){
- x1=_x1;
- y1=_y1;
- x2=_x2;
- y2=_y2;
- area=_area;
- }
- }rect[N],left[N*N];
- inline bool cmp(const Rect&a,const Rect&b){return a.area<b.area;}
- void init(int*a,int&n){
- int m=0,i;
- sort(a+1,a+n+1);
- for(i=1;i<=n;i++)if(i==1||a[i]>a[m])a[++m]=a[i];
- n=m;
- }
- void cov(int A,int B,int C,int D,ull E){
- int i,j;
- for(i=1;i<=ca;i++)if(a[i]>=A&&a[i+1]<=B)for(j=1;j<=cb;j++)if(b[j]>=C&&b[j+1]<=D)col[i][j]^=E;
- }
- void dfs(int x,int y){
- if(x<1||x>ca||y<1||y>cb)return;
- if(col[x][y]!=goal)return;
- if(vis[x][y])return;
- vis[x][y]=1;
- area+=(a[x+1]-a[x])*(b[y+1]-b[y]);
- xl=min(xl,a[x]);
- xr=max(xr,a[x+1]);
- yl=min(yl,b[y]);
- yr=max(yr,b[y+1]);
- dfs(x-1,y);
- dfs(x+1,y);
- dfs(x,y-1);
- dfs(x,y+1);
- }
- inline bool inside(const Rect&A,const Rect&B){
- return A.x1>=B.x1&&A.x2<=B.x2&&A.y1>=B.y1&&A.y2<=B.y2;
- }
- bool find(int x){
- while(1){
- U t=v&g[x];
- if(!t)return 0;
- int y=__builtin_ctz(t);
- v^=1U<<y;
- if(!f[y]||find(f[y]))return f[y]=x,1;
- }
- return 0;
- }
- int main(){
- scanf("%d",&n);
- for(i=1;i<=n;i++)scanf("%d",&rect[i].x1);
- for(i=1;i<=n;i++)scanf("%d",&rect[i].y1);
- for(i=1;i<=n;i++)scanf("%d",&rect[i].x2);
- for(i=1;i<=n;i++)scanf("%d",&rect[i].y2);
- for(i=1;i<=n;i++){
- a[++ca]=rect[i].x1,a[++ca]=rect[i].x2;
- b[++cb]=rect[i].y1,b[++cb]=rect[i].y2;
- }
- init(a,ca);
- init(b,cb);
- ca--,cb--;
- for(i=1;i<=n;i++)w[i]=w[i-1]*233+10007;
- for(i=1;i<=n;i++)cov(rect[i].x1,rect[i].x2,rect[i].y1,rect[i].y2,w[i]);
- for(i=1;i<=ca;i++)for(j=1;j<=cb;j++)if(!vis[i][j]&&col[i][j]){
- xl=inf,xr=-inf;
- yl=inf,yr=-inf;
- area=0;
- goal=col[i][j];
- dfs(i,j);
- if((xr-xl)*(yr-yl)==area)left[++m]=Rect(xl,yl,xr,yr,area);
- }
- sort(left+1,left+m+1,cmp);
- for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(inside(left[i],rect[j]))g[i]|=1U<<(j-1);
- for(i=1;i<=m;i++){
- v=(1U<<n)-1;
- if(find(i))cnt++,ans+=left[i].area;
- }
- if(cnt<n)ans=-1;
- return printf("%d",ans),0;
- }
来源: http://www.bubuko.com/infodetail-3367618.html