yukicoder : No.2769 Number of Rhombi

今回は割とすんなり。
https://yukicoder.me/problems/no/2769

問題

2次元座標上でN個の点が与えられる。
4点の組のうちひし形を成すものは何通りか。

解法

4点がひし形を成すには、2本の対角線の中点が一致し、かつ対角線が直角に交わればよい。
そこで、2点の対を総当たりし、中点の座標と対角線の傾きを数え上げて行こう。

int N;
ll X[1010],Y[1010];

map<pair<pair<ll,ll>,pair<ll,ll>>,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	ll ret=0;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		FOR(j,i) {
			ll sx=X[i]+X[j];
			ll sy=Y[i]+Y[j];
			ll dx=X[i]-X[j];
			ll dy=Y[i]-Y[j];
			if(dx<0) {
				dx=-dx;
				dy=-dy;
			}
			if(dx==0) dy=abs(dy);
			ll g=__gcd(abs(dx),abs(dy));
			dx/=g;
			dy/=g;
			M[{{sx,sy},{dx,dy}}]++;
			
			if(dx==0) {
				ret+=M[{{sx,sy},{1,0}}];
			}
			else if(dy==0) {
				ret+=M[{{sx,sy},{0,1}}];
			}
			else {
				swap(dx,dy);
				dx=-dx;
				if(dx<0) {
					dx=-dx;
					dy=-dy;
				}
				if(dx==0) dy=abs(dy);
				
				ret+=M[{{sx,sy},{dx,dy}}];
			}
			
		}
		
	}
	cout<<ret<<endl;
}

まとめ

正方形や長方形を数える問題は多いけど、ひし形は珍しい印象。