AtCoder ABC #131 : F - Must Be Rectangular!

こういうの何度か見たので本番４分ぐらいで解いてた。
https://atcoder.jp/contests/abc131/tasks/abc131_f

問題

二次元座標上でN個の格子点が与えられる。
このうち３点が、軸に平行な長方形の３頂点に位置している場合、残り1か所に点を追加する。
これ以上点が増えなくなるまで点を増やすと、最終的に何個増えた状況になるか。

解法

X座標が同じ、またはY座標が同じ点同士をUnion-Findで連結しよう。
連結成分について、そこに登場するX座標・Y座標の組み合わせはすべて最終的に点が埋められるので、各連結成分に現れるユニークなX座標・Y座標の個数を数えて掛け合わせていけばよい。

int N;
map<int,int> Xs;
map<int,int> Ys;
int X[101010],Y[101010];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

set<int> PX[101010],PY[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		if(Xs.count(X[i])) uf(i,Xs[X[i]]);
		Xs[X[i]]=i;
		if(Ys.count(Y[i])) uf(i,Ys[Y[i]]);
		Ys[Y[i]]=i;
	}
	FOR(i,N) {
		PX[uf[i]].insert(X[i]);
		PY[uf[i]].insert(Y[i]);
	}
	ll ret=0;
	FOR(i,N) ret+=1LL*PX[i].size()*PY[i].size();
	cout<<ret-N<<endl;
}

まとめ

600ptとはいえ既出すぎでは…と思ったけど、ABCなのでってことなのかな。