算法分析

不妨维护行与列的连通性，考虑对于点$(x,y)$，把行$x$和列$y$合并在一起。最终，对于形成的每个连通块(不妨定义为每个集合内的行、列的所有交点，而不是框起来的部分)，其内部所有空白的点一定可以与另外三个给定的点形成一个矩形:多个连通块之间的点不能形成矩形。

因此，设每个连通块包含的行和列的数量为 $a_i,b_i$，答案为$\sum {a_i b_i} -n$

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=1e5;
typedef long long LL;
LL p[N],a[N],b[N];

int find(int x)
{
	if(x!=p[x])
	{
		p[x]=find(p[x]);
	}
	return p[x];
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=M+M;i++)
	{
		p[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		y+=M;
		x=find(x),y=find(y);
		if(x!=y) //不在同一个集合之中 
		{
			p[x]=y;
		}
		//cout<<x<<" "<<y<<endl;
	}
	for(int i=1;i<=M;i++) //统计x出现的个数 
	{
		b[find(i)]++;
	}
	for(int i=M+1;i<=M+M;i++) //统计y出现的次数 
	{
		a[find(i)]++;
	}
	LL ans=0;
	for(int i=1;i<=M+M;i++)
	{
		ans+=a[i]*b[i];	
	} 
	cout<<ans-n;
	return 0;
}