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