Đếm hình bình hành trong mặt phẳng trong C++

Cho các điểm trên mặt phẳng. Đếm số hình bình hành có thể tạo thành. Tính chất: Đối角线 của hình bình hành cắt nhau tại trung điểm.

Giải thuật: Với mỗi cặp điểm (i,j), tính trung điểm ((x_i+x_j)/2, (y_i+y_j)/2). Đếm số cặp có cùng trung điểm. Nếu có k cặp cùng trung điểm thì tạo được C(k,2) hình bình hành.

Ví dụ: Điểm tạo 3 hình bình hành.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

int parallelogram(int a[], int b[], int size) {
    map<pair<int,int>, int> um;
    int count = 0;
    for (int i = 0; i < size; i++)
        for (int j = i+1; j < size; j++) {
            int mx = a[i] + a[j];
            int my = b[i] + b[j];
            um[{mx, my}]++;
        }
    for (auto it : um) {
        int t = it.second;
        count += t * (t - 1) / 2;
    }
    return count;
}

int main() {
    int a[] = {0,3,1,4,1,5};
    int b[] = {0,1,3,4,4,4};
    int size = sizeof(a) / sizeof(int);
    cout << "Count: " << parallelogram(a, b, size);
    return 0;
}

Đầu ra

Count of parallelograms in a plane: 1