更差的閱讀體驗(yàn)

注意到，增加一個(gè)障礙物至少可以減少一對(duì)互相攻擊的車，最多減少兩對(duì)互相攻擊的車。

考慮兩對(duì)車什么時(shí)候可以同時(shí)消除，當(dāng)且僅當(dāng)兩對(duì)車的連線有交。所以可以轉(zhuǎn)換成一個(gè)二分圖匹配的模型，具體地，每個(gè)左部點(diǎn)是每一對(duì)橫坐標(biāo)相同的可以相互攻擊的車，右部點(diǎn)是每一對(duì)縱坐標(biāo)相同可以相互攻擊的車。如果一對(duì)車可以同時(shí)消除，則在這兩對(duì)點(diǎn)中間連邊。

假設(shè)左部點(diǎn)個(gè)數(shù)為 \(s_1\)，右部點(diǎn)個(gè)數(shù)為 \(s_2\)，答案就是 \(s_1+s_2-\text{match}\)，其中 \(\text{match}\) 表示二分圖最大匹配。

關(guān)于如何輸出方案，可以用網(wǎng)絡(luò)流求匹配，然后在殘量網(wǎng)絡(luò)上看每條邊上面有沒有流量就可以了。

然后這道題就做完了。中間邊數(shù) \(m=O(n^2)\)，復(fù)雜度是 \(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 dyc2022
	int 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;
}