[POJ] 1971 - Parallelogram Counting - http://kuoe0.ch/386/poj-1971-parallelogram-counting/

1971 - Parallelogram Counting.cpp

#include <iostream>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct POINT {
	int x, y;
	bool operator< ( const POINT r ) const {
		return ( x < r.x ) || ( x == r.x && y < r.y );
	}
	bool operator== ( const POINT r ) const {
		return x == r.x && y == r.y;
	}
};

POINT pt[ 1010 ], temp, mid[ 1000010 ];
map< POINT, int > cnt;

int main() {
	int t, n;
	scanf( "%d", &t );
	while ( t-- ) {
		cnt.clear();
		scanf( "%d", &n );
		for ( int i = 0; i < n; ++i )
			scanf( "%d %d", &pt[ i ].x, &pt[ i ].y );
		
		int m = 0, ret = 0;

		for ( int i = 0; i < n; ++i )
			for ( int j = i + 1; j < n; ++j ) {
				mid[ m ].x = pt[ i ].x + pt[ j ].x;
			   	mid[ m ].y = pt[ i ].y + pt[ j ].y;
				++m;
			}
		sort( mid, mid + m );
		int x = 1;
		for ( int i = 1; i < m; ++i )
			if ( mid[ i ] == mid[ i - 1 ] )
				++x;
			else if ( x > 1 )
				ret += ( x * ( x - 1 ) ) >> 1, x = 1;
		printf( "%d\n", ret );
	}
	return 0;
}