題目網址：1971 - Parallelogram Counting

題目概述

給定二維平面上 N 個點，求出有幾種組合可以形成平行四邊形。

Technique Detail

• 點的數量 N, 1 ≤ N ≤ 1,000

輸入格式

測試資料由一個整數 K 開始，表示接下來有 K 組測試資料。

每一筆測試資料由一個整數 N 開始，表示平面上有 N 個點。接下來有 N 行，每行兩個整數 x_i y_i ，表示該點座標。

輸出格式

對於每一筆測試資料，輸出只有一行，且只含有一個整數，即為可以形成平行四邊形的組合數量。

---

解題思路

枚舉兩個點，並記錄所有中點。若有重複的中點，即可從這些點中，任取兩個出來組成一個平行四邊形。平行四邊形的兩對角線中點會重合，故此方法可行。對所有中點排序後，即可快速找出重複的中點。

中點的數量會有 C(N, 2) 個，大約為 N² 個。因此排序的時間為 O( N² × log N²)

Time Complexity: O( N² × log N²)

Source Code

	#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;
	}

view raw 1971 - Parallelogram Counting.cpp hosted with ❤ by GitHub

Source code on gist.