Skip to content

Instantly share code, notes, and snippets.

@kuoe0
Created January 14, 2012 16:52
Show Gist options
  • Save kuoe0/1612017 to your computer and use it in GitHub Desktop.
Save kuoe0/1612017 to your computer and use it in GitHub Desktop.
[POJ] 1971 - Parallelogram Counting - http://kuoe0.ch/386/poj-1971-parallelogram-counting/
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment