นับคู่แฝด (A, B, C) ของคะแนนในพื้นที่ 2 มิติที่ตรงตามเงื่อนไขที่กำหนดใน C++

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

เราจะทำสิ่งนี้โดยการแทรกจุดทั้งหมดเป็นคู่ ลงในเวกเตอร์ จากนั้นเพิ่มคู่ทั้งหมดจากเวกเตอร์นี้ในชุด โดยนำจุดสองจุดจากเซตตรวจสอบว่าผลรวมของพิกัด (x,y) หารด้วย 2 อยู่ในเซตเดียวกันหรือไม่ ถ้าใช่ ให้เพิ่มจำนวนแฝด

มาทำความเข้าใจกับตัวอย่างกัน

ป้อนข้อมูล

{ 1,2 }, { 4,2} , { 2,1 } , { 7,2 } N=4 pairs

ผลผลิต

Count of triplet pairs that satisfy the given condition are: 1

คำอธิบาย

Here {4,2} is mid-point between {1,2} and {7,2}. Only 1 such triplet

ป้อนข้อมูล

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

ผลผลิต

Count of triplet pairs that satisfy the given condition are: 1

คำอธิบาย

No such triplet exist

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• เรากำลังหาเวกเตอร์ของคู่ของประเภท .

• แต่ละคู่ประกอบด้วยพิกัด (x,y)

• ฟังก์ชัน mid_point(vector> vec, int size) ใช้เวกเตอร์และมีขนาดเป็นอินพุตและส่งกลับจำนวน triplets ที่ตรงตามเงื่อนไขจุดกึ่งกลาง

• นับตัวแปรเริ่มต้นเป็น 0 สำหรับแฝดสามดังกล่าว

• แทรกคู่ทั้งหมดจากเวกเตอร์ลงใน set> sets มันจะมีจุดเฉพาะทั้งหมด

• ข้ามเวกเตอร์โดยใช้สองลูปสำหรับจุดแต่ละคู่

• เก็บผลรวมของพิกัด x ของทั้งสองจุดเป็นจำนวนเต็ม point_A และผลรวมของพิกัด y ของทั้งสองจุดในจุดจำนวนเต็ม_B

• หากผลรวมใน point_A และ point_B เป็นคู่ ให้ตรวจสอบเงื่อนไขจุดกึ่งกลาง

• หากมีคู่ (point_A/2,point_B/2) เป็นคู่ในชุดหมายความว่ามีจุดกึ่งกลางอยู่ จำนวนที่เพิ่มขึ้นของแฝด

• ในตอนท้ายจะมีจำนวนแฝดสาม

• คืนค่าการนับเป็นผลเมื่อสิ้นสุดลูป for

ตัวอย่าง

#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<<"Count of triplet pairs (A, B, C) of points in 2-D space that satisfy the given condition are: "<<mid_point(vec, size);
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of triplet pairs (A, B, C) of points in 2-D space that satisfy the given condition are: 1