记矩形的并为 \(P\)，定义多边形的大小为它的顶点个数 \(|P|\)，其 \(90\)°的顶角为凸角，\(270\)°的顶角为凹角并记凹点构成的集合为 \(C\)，称竖直或水平在多边形内部分割开矩形的线为割线，连接了两个凹点的割线为好割线
贪心可以发现对于 \(P\) 的任意极小矩阵划分，所有的割线至少有一端是 \(P\) 上的凹点，即存在一个端点 \(\in C\)，否则一定可以合并此割线两边的矩形
对于任意一个 \(P\) 的极小矩形剖分 \(R\) 及关于 \(R\) 的不相交的好割线集合 \(N\) 有 \(4|R|=|P|+2|C|-4|N|\)，考虑利用内角和的变化证明，它原本的内角和等于 \(90\)°\(\times\) 凸点数\(+270\)°\(\times\) 凹点数\(=(|P|+2|C|)\times 90\)°，对于每一条 \(N\) 中的好割线将每个端点切为 \(90\)°与 \(180\)°两部分，前者构成最终矩阵的内角后者构成一条边，那么增量为 \(-2 \times 180\)°，对于不在 \(N\) 中的割线 \(a=(x,y)\)，若 \(x\in C \wedge y \notin C\)，那么它会将一条边或割线分为两个角从而与 \(x\) 带来的负增量抵消，否则 \(y\) 一定被其它割线分割从而与 \(y \notin C\) 的情况相同
考虑最大化 \(|N|\)，由于只有竖直与水平的割线会相交，将竖直的好割线看作二分图左部点，水平的看作右部点，它们的交点看作它们之间的连边，那么所求转化为此图的最大独立集，使用网络流求解即可，考虑求解 \(|P|\) 与 \(|C|\)，可以枚举每个四连通块，若只有一个点被覆盖则 \(|P| \leftarrow |P|+1\)，至于两个多边形的一角重合的情况与 \(|C|\)，钦定四联通块的右上角没有被覆盖并枚举其四个方向的被覆盖情况即可，考虑如何建图，将矩形离散化后可以使用二维数组模拟，找出所有凹点坐标后可以 \(\text{O}(|P|^2)\) 枚举并 \(\text{O}(k)\) 延展枚举另一个端点，由于每个凹点最多属于一个水平与竖直割线，所以均摊复杂度正确，再枚举它们是否相交即可
#include<bits/stdc++.h>
using namespace std;
int k,h,w,s,t,n,m,ans,val,tot=1,flow,l[301],p[301],r[301],q[301],d[701][701],c[701][701],head[8001],now[8001],dep[8001],nex[800001],edge[800001],ver[800001];
basic_string <int> vx,vy;
basic_string <tuple<int,int,int,int>> ux,uy;
void add(int u,int v,int w){
ver[++tot]=v,edge[tot]=w,nex[tot]=head[u],head[u]=tot;
ver[++tot]=u,edge[tot]=0,nex[tot]=head[v],head[v]=tot;
}
int bfs(){
queue <int> q;
for(int i=s;i<=t;i++) dep[i]=0,now[i]=head[i];
dep[s]=1,q.push(s);
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nex[i]){
if(edge[i]&&!dep[ver[i]]){
dep[ver[i]]=dep[x]+1;
q.push(ver[i]);
if(ver[i]==t) return 1;
}
}
}
return 0;
}
int dinic(int x,int flow){
if(x==t) return flow;
int rest=flow,k=0;
for(int i=now[x];i&&rest;i=nex[i]){
now[x]=i;
if(edge[i]&&dep[ver[i]]==dep[x]+1){
k=dinic(ver[i],min(edge[i],rest));
if(!k) dep[ver[i]]=0;
rest-=k;
edge[i]-=k;
edge[i^1]+=k;
}
}
return flow-rest;
}
int main(){
scanf("%d",&k);
for(int i=1;i<=k;i++) scanf("%d%d%d%d",&l[i],&p[i],&r[i],&q[i]),vx+=l[i],vx+=++r[i],vy+=p[i],vy+=++q[i];
sort(begin(vx),end(vx)),vx.erase(unique(begin(vx),end(vx)),end(vx)),h=vx.size();
sort(begin(vy),end(vy)),vy.erase(unique(begin(vy),end(vy)),end(vy)),w=vy.size();
for(int i=1;i<=k;i++){
l[i]=lower_bound(vx.begin(),vx.end(),l[i])-vx.begin()+1;
r[i]=lower_bound(vx.begin(),vx.end(),r[i])-vx.begin()+1;
p[i]=lower_bound(vy.begin(),vy.end(),p[i])-vy.begin()+1;
q[i]=lower_bound(vy.begin(),vy.end(),q[i])-vy.begin()+1;
d[l[i]][p[i]]++,d[l[i]][q[i]]--,d[r[i]][p[i]]--,d[r[i]][q[i]]++;
}
for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) d[i][j]=d[i][j]>0;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
int cnt=d[i][j]+d[i-1][j]+d[i][j-1]+d[i-1][j-1];
if(cnt==3) c[i][j]=1;
if(cnt==1) ans++;
if(!d[i][j]&&d[i-1][j]&&d[i][j-1]) ans++;
if(!d[i][j]&&d[i+1][j]&&d[i][j-1]) ans++;
if(!d[i][j]&&d[i-1][j]&&d[i][j+1]) ans++;
if(!d[i][j]&&d[i+1][j]&&d[i][j+1]) ans++;
if(!d[i][j]&&d[i-1][j]&&d[i][j-1]&&d[i-1][j-1]) ans+=2;
if(!d[i][j]&&d[i-1][j]&&d[i][j+1]&&d[i-1][j+1]) ans+=2;
if(!d[i][j]&&d[i+1][j]&&d[i][j-1]&&d[i+1][j-1]) ans+=2;
if(!d[i][j]&&d[i+1][j]&&d[i][j+1]&&d[i+1][j+1]) ans+=2;
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(c[i][j]){
if(d[i-1][j]&&d[i][j]){
int k=j;
while(d[i-1][k]&&d[i][k]) k++;
if(c[i][k]) ux+={i,i,j,k};
}
if(d[i][j-1]&&d[i][j]){
int k=i;
while(d[k][j-1]&&d[k][j]) k++;
if(c[k][j]) uy+={i,k,j,j};
}
}
}
}
n=ux.size(),m=uy.size(),val=n+m,t=n+m+1;
for(int i=1;i<=n;i++) add(s,i,1);
for(int i=1;i<=m;i++) add(i+n,t,1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
auto [a,b,c,d]=ux[i-1];
auto [e,f,g,h]=uy[j-1];
if(e<=a&&a<=f&&c<=g&&g<=d) add(i,j+n,1);
}
}
while(bfs()) while(flow=dinic(s,1e9)) val-=flow;
printf("%d",(ans-val*4)/4);
return 0;
}