Codeforces #345 Div1. A. Watchmen

平日変な時間帯なので不参加。ABCはすんなり解けてたので、D解けなくてもレート微増は出来てたな…もったいない。
http://codeforces.com/contest/650/problem/A

問題

2次元座標上でN個の点が与えられる。
これらの点のうち2点選んだ時、ユークリッド距離とマンハッタン距離が等しくなるものの組み合わせを求めよ。

解法

条件を満たすのは、X座標かY座標が一致するもの。
よって、X座標別・Y座標別に登場する頂点数をカウントし、同じX座標またはY座標の点を2つ取る組み合わせの総和を取ればよい。

この問題は同じ座標に複数頂点がある場合があるので、二重カウントした分は除いておこう。

int N;
map<ll,ll> XX;
map<ll,ll> YY;
map<pair<ll,ll>,ll> XY;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		XX[x]++;
		YY[y]++;
		XY[{x,y}]++;
	}
	ll ret=0;
	FORR(r,XX) ret+=r.second*(r.second-1)/2;
	FORR(r,YY) ret+=r.second*(r.second-1)/2;
	FORR(r,XY) ret-=r.second*(r.second-1)/2;
	cout<<ret<<endl;
}

まとめ

Div1Aとしてはシンプルで簡単な問題。