Đếm số bộ ba điểm (A, B, C) trong không gian 2-D thỏa mãn điều kiện điểm giữa trong C++

Chúng ta được cho N điểm trên mặt phẳng 2-D. Mục tiêu là đếm số lượng bộ ba điểm từ đầu vào sao cho một điểm là trung điểm của đoạn thẳng nối hai điểm còn lại. Tức là nếu bộ ba là (A, B, C) thì B là trung điểm của A và C (hoặc bất kỳ tổ hợp nào của A, B, C).

Chúng ta sẽ thực hiện bằng cách đưa tất cả các điểm dưới dạng cặp <int, int> vào một vector. Sau đó thêm tất cả các cặp từ vector này vào một set. Lấy hai điểm từ set, kiểm tra xem tổng tọa độ (x, y) chia cho 2 có tồn tại trong cùng set đó hay không. Nếu có, tăng biến đếm bộ ba.

Hãy hiểu qua các ví dụ.

Đầu vào

{ 1,2 }, { 4,2 }, { 2,1 }, { 7,2 } N=4 cặp

Đầu ra

Số bộ ba thỏa mãn điều kiện là: 1

Giải thích

Ở đây {4,2} là trung điểm của {1,2} và {7,2}. Chỉ có 1 bộ ba như vậy

Đầu vào

{ 1,2 }, { 4,2 }, { 2,1 }, { 5,2 }, { 8,1 }, {1,1} N=6

Đầu ra

Số bộ ba thỏa mãn điều kiện là: 1

Giải thích

Không tồn tại bộ ba nào

Phương pháp sử dụng trong chương trình dưới đây

Sử dụng vector các cặp kiểu <int, int>.
Mỗi cặp chứa tọa độ (x, y).
Hàm mid_point(vector<pair<int, int>> vec, int size) nhận vector và kích thước của nó làm đầu vào, trả về số bộ ba thỏa mãn điều kiện trung điểm.
Khởi tạo biến count = 0 cho số bộ ba.
Chèn tất cả các cặp từ vector vào set<pair<int, int>> sets. Set sẽ chứa các điểm duy nhất.
Duyệt vector bằng hai vòng lặp for cho mỗi cặp điểm.
Lưu tổng tọa độ x của hai điểm vào biến nguyên point_A và tổng tọa độ y vào point_B.
Nếu cả hai tổng này đều chẵn thì kiểm tra điều kiện trung điểm.
Nếu cặp (point_A/2, point_B/2) tồn tại trong set nghĩa là trung điểm tồn tại. Tăng biến đếm bộ ba.
Cuối cùng count sẽ chứa số lượng bộ ba.
Trả về count làm kết quả sau khi kết thúc vòng lặp.

Ví dụ

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

int mid_point(vector<pair<int, int>> vec, int size) {
    int count = 0;
    set<pair<int, int>> sets;
    for (int i = 0; i < size; i++) {
        sets.insert(vec[i]);
    }
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            int point_A = vec[i].first + vec[j].first;
            int point_B = vec[i].second + vec[j].second;
            if (point_A % 2 == 0 && point_B % 2 == 0) {
                if (sets.find(make_pair(point_A / 2, point_B / 2)) != sets.end()) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    vector<pair<int, int>> vec = { { 9, 2 }, { 5, 2 }, { 1, 2 } };
    int size = vec.size();
    cout << "Số bộ ba điểm (A, B, C) trong không gian 2-D thỏa mãn điều kiện là: " << mid_point(vec, size);
    return 0;
}

Đầu ra

Nếu chạy mã trên sẽ cho kết quả sau:

Số bộ ba điểm (A, B, C) trong không gian 2-D thỏa mãn điều kiện là: 1