นับจำนวนคู่สามจุด (A, B, C) ในพื้นที่ 2 มิติที่เป็นจุดกึ่งกลางระหว่างสองจุดที่เหลือใน C++

ภาพรวมปัญหา

ให้ชุดของจุด N จุดบนพื้นที่ 2 มิติ เป้าหมายคือการนับจำนวน triplet (A, B, C) ที่จุดหนึ่งเป็นจุดกึ่งกลางของเส้นตรงที่เชื่อมต่ออีกสองจุด กล่าวคือ B เป็นจุดกึ่งกลางของ A และ C (หรือการจัดเรียงอื่นๆ ของ A, B, C)

แนวคิดหลัก

• เก็บจุดทั้งหมดเป็นคู่ <int, int> ใน vector
• นำจุดทั้งหมดเข้าไปใน set เพื่อความเป็นเอกลักษณ์และการค้นหาเร็ว
• เลือกคู่จุดสองจุดจากชุด ตรวจสอบว่าจุดกึ่งกลาง (ค่าเฉลี่ยของ x และ y) มีอยู่ใน set หรือไม่
• ถ้ามี ให้เพิ่มจำนวน triplet

ตัวอย่าง

Input: {1,2}, {4,2}, {2,1}, {7,2} (N=4)

Output: 1

คำอธิบาย: จุด {4,2} เป็นจุดกึ่งกลางระหว่าง {1,2} และ {7,2}

ขั้นตอนการทำงาน

1. สร้าง vector ของ pair<int, int> สำหรับเก็บพิกัด (x, y)
2. ฟังก์ชัน mid_point(vector<pair<int, int>> vec, int size) คืนค่าจำนวน triplet ที่ตรงเงื่อนไข
3. ตัวแปร count เริ่มต้นที่ 0
4. แทรกจุดทั้งหมดจาก vector ลงใน set<pair<int, int>>
5. ใช้ nested loop เลือกคู่จุด (i, j) โดย i < j
6. คำนวณ point_A = vec[i].first + vec[j].first และ point_B = vec[i].second + vec[j].second
7. ถ้า point_A และ point_B เป็นเลขคู่ (หาร 2 ลงตัว) ให้ตรวจสอบว่า (point_A/2, point_B/2) อยู่ใน set หรือไม่
8. ถ้าอยู่ ให้เพิ่ม count
9. คืนค่า count

โค้ดตัวอย่าง

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

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

int main() {
    vector<pair<int, int>> vec = {{9, 2}, {5, 2}, {1, 2}};
    int size = vec.size();
    cout << "Count of triplet pairs: " << mid_point(vec, size);
    return 0;
}

ผลลัพธ์

Count of triplet pairs: 1

ความซับซ้อนของอัลกอริทึม

• เวลา: O(N² log N) - nested loop N² ครั้ง พร้อมการค้นหาใน set ใช้ log N
• พื้นที่: O(N) - สำหรับเก็บจุดใน set