POJ 1971 Parallelogram Counting

問題

2次元平面上の整数座標がn点（n<=1000）与えられる。4点を選んでできる平行四辺形の個数を求めよ。ただしどの4点も一直線上に並ばないものとする。

やりかた

3点を指定すると残り1点が定まり、その残りの点が与えられた中にあるかを調べる、というやりかただとTLEしてしまう。
2点を指定するとその2点の中点が定まる。このとき別の2点の中点がこの中点と同じだとすると、そこで一つの平行四辺形ができる。こう考えると、2点の中点をすべて列挙し、とある中点がkペアの2点の中点となっていたら、その中点を中心に個の平行四辺形ができるわけだから、これを足し上げていけばいい。計算量
ただ、G++で中点の頻度を

map<pair<long long, long long>, int> 

で管理したらTLEしたのですこし工夫した。あと、中点は整数になっていてほしいので得られた座標を原点基準で2倍することで必ず中点が整数になるようにしている。

以下ソース。

ll x[1000], y[1000];

ll base = 5000000000;

int main(){
  int t;
  scanf("%d", &t);
  while(t--){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
      scanf("%lld %lld", x + i, y + i);
      x[i] *= 2LL;
      y[i] *= 2LL;
    }

    int idx = 0;
    vector<ll> p(n * (n - 1) / 2);
    for(int i = 0; i < n; i++){
      for(int j = i + 1; j < n; j++){
	ll cx = (x[i] + x[j]) / 2;
	ll cy = (y[i] + y[j]) / 2;

	p[idx++] = cy * base + cx;
      }
    }
    sort(ALL(p));

    int c = 1;
    int ans = 0;
    for(int i = 1; i < p.size(); i++){
      if(p[i] == p[i - 1]) c++;
      else{
	ans += (c * (c - 1) / 2);
	c = 1;
      }
    }
    ans += (c * (c - 1) / 2);

    cout << ans << endl;
  }
  return 0;
}

1000msくらいだった