更差的阅读体验
注意到，增加一个障碍物至少可以减少一对互相攻击的车，最多减少两对互相攻击的车。
考虑两对车什么时候可以同时消除，当且仅当两对车的连线有交。所以可以转换成一个二分图匹配的模型，具体地，每个左部点是每一对横坐标相同的可以相互攻击的车，右部点是每一对纵坐标相同可以相互攻击的车。如果一对车可以同时消除，则在这两对点中间连边。
假设左部点个数为 \(s_1\)，右部点个数为 \(s_2\)，答案就是 \(s_1+s_2-\text{match}\)，其中 \(\text{match}\) 表示二分图最大匹配。
关于如何输出方案，可以用网络流求匹配，然后在残量网络上看每条边上面有没有流量就可以了。
然后这道题就做完了。中间边数 \(m=O(n^2)\)，复杂度是 \(O(m \sqrt m) = O(n^3)\)。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 10006
using namespace std;
struct Node {int x,y,typ;void read(){scanf("%lld%lld",&x,&y);}
}a[N],c[N];
int T,n,m,bnx,bx[N],bny,by[N];
vector<Node> row[N],col[N];
vector<pair<Node,Node> > Row,Col;
vector<pair<pair<int,Node>,pair<pair<Node,Node>,pair<Node,Node> > > > vec;
struct MF_Graph{//by dyc2022int head[N],cnt=2,s,t,now[N],dep[N];struct Edge{int to,next,w;}E[N];void addedge(int u,int v,int w){E[cnt]={v,head[u],w},head[u]=cnt++;}void addflow(int u,int v,int w){addedge(u,v,w),addedge(v,u,0);}void init(){memset(head,0,sizeof(head)),cnt=2,s=t=0;memset(now,0,sizeof(now));memset(dep,0,sizeof(dep));for(int i=0;i<N;i++)E[i].to=E[i].next=E[i].w=0;}int bfs(){queue<int> q;memset(dep,-1,sizeof(dep));dep[s]=0,now[s]=head[s],q.push(s);while(q.size()){int u=q.front();q.pop();for(int i=head[u],v,w;i;i=E[i].next){v=E[i].to,w=E[i].w;if(dep[v]==-1&&w>0){dep[v]=dep[u]+1,now[v]=head[v],q.push(v);;if(v==t)return 1;}}}return 0;}int dfs(int u,int fl){if(u==t)return fl;int ret=0;for(int i=now[u],v,w;i&&fl>0;i=E[i].next){v=E[i].to,w=E[i].w,now[u]=i;if(dep[v]==dep[u]+1&&w>0){int tmp=dfs(v,min(fl,w));if(!tmp)dep[v]=-1;E[i].w-=tmp,E[i^1].w+=tmp,fl-=tmp,ret+=tmp;}}return ret;}int getflow(){int ret=0;while(bfs())ret+=dfs(s,1e15);return ret;}
}G;
Node get(pair<Node,Node> p,pair<Node,Node> q)
{Node ret;ret.x=p.first.x,ret.y=q.first.y;int lx=q.first.x,rx=q.second.x;int ly=p.first.y,ry=p.second.y;if(ret.x<=lx||ret.x>=rx||ret.y<=ly||ret.y>=ry)ret.x=ret.y=-1;return ret;
}
Node get2(pair<Node,Node> p)
{Node ret;if(p.first.x==p.second.x)ret.x=bx[p.first.x],ret.y=by[p.first.y]+1;else ret.x=bx[p.first.x]+1,ret.y=by[p.first.y];return ret;
}
bool operator ==(pair<Node,Node> p,pair<Node,Node> q)
{return p.first.x==q.first.x&&p.first.y==q.first.y&&p.second.x==q.second.x&&p.second.y==q.second.y;
}
void solve()
{scanf("%lld",&n);for(int i=1;i<=n;i++)a[i].read(),a[i].typ=0;scanf("%lld",&m);for(int i=1;i<=m;i++)c[i].read(),c[i].typ=1;bnx=0;for(int i=1;i<=n;i++)bx[++bnx]=a[i].x;for(int i=1;i<=m;i++)bx[++bnx]=c[i].x;sort(bx+1,bx+1+bnx),bnx=unique(bx+1,bx+1+bnx)-bx-1;for(int i=1;i<=n;i++)a[i].x=lower_bound(bx+1,bx+1+bnx,a[i].x)-bx;for(int i=1;i<=m;i++)c[i].x=lower_bound(bx+1,bx+1+bnx,c[i].x)-bx;bny=0;for(int i=1;i<=n;i++)by[++bny]=a[i].y;for(int i=1;i<=m;i++)by[++bny]=c[i].y;sort(by+1,by+1+bny),bny=unique(by+1,by+1+bny)-by-1;for(int i=1;i<=n;i++)a[i].y=lower_bound(by+1,by+1+bny,a[i].y)-by;for(int i=1;i<=m;i++)c[i].y=lower_bound(by+1,by+1+bny,c[i].y)-by;for(int i=1;i<=bnx;i++)row[i].clear();for(int i=1;i<=bny;i++)col[i].clear();Col.clear(),Row.clear(),vec.clear();for(int i=1;i<=n;i++)row[a[i].x].push_back(a[i]),col[a[i].y].push_back(a[i]);for(int i=1;i<=m;i++)row[c[i].x].push_back(c[i]),col[c[i].y].push_back(c[i]);for(int i=1;i<=bnx;i++){sort(row[i].begin(),row[i].end(),[](Node x,Node y) {return x.y<y.y;});int sz=row[i].size();for(int j=0;j<sz-1;j++)if(!row[i][j].typ&&!row[i][j+1].typ)Row.push_back({row[i][j],row[i][j+1]});}for(int i=1;i<=bny;i++){sort(col[i].begin(),col[i].end(),[](Node x,Node y) {return x.x<y.x;});int sz=col[i].size();for(int j=0;j<sz-1;j++)if(!col[i][j].typ&&!col[i][j+1].typ)Col.push_back({col[i][j],col[i][j+1]});}for(auto i:Row)if(by[i.first.y]+1==by[i.second.y])return printf("-1\n"),(void)0;for(auto i:Col)if(bx[i.first.x]+1==bx[i.second.x])return printf("-1\n"),(void)0;int sz_row=Row.size(),sz_col=Col.size();G.init(),G.s=sz_row+sz_col+1,G.t=G.s+1;for(int i=0;i<sz_row;i++)G.addflow(G.s,i+1,1);for(int i=0;i<sz_col;i++)G.addflow(i+sz_row+1,G.t,1);for(int i=0;i<sz_row;i++)for(int j=0;j<sz_col;j++){Node tmp=get(Row[i],Col[j]);if(tmp.x==-1||tmp.y==-1)continue;G.addflow(i+1,j+sz_row+1,1),vec.push_back({{G.cnt-1,tmp},{Row[i],Col[j]}});}int max_flow=G.getflow();printf("%lld\n",sz_row+sz_col-max_flow);vector<pair<Node,Node> > tmp;for(auto i:vec)if(G.E[i.first.first].w){printf("%lld %lld\n",bx[i.first.second.x],by[i.first.second.y]);tmp.push_back(i.second.first),tmp.push_back(i.second.second);}for(auto i:Row){int flag=0;for(auto j:tmp)flag|=(i==j);if(flag)continue;Node t=get2(i);printf("%lld %lld\n",t.x,t.y);}for(auto i:Col){int flag=0;for(auto j:tmp)flag|=(i==j);if(flag)continue;Node t=get2(i);printf("%lld %lld\n",t.x,t.y);}
}
main()
{scanf("%lld",&T);while(T--)solve();return 0;
}