Chúng tôi được cung cấp đầu vào của N điểm trên không gian 2-D. Mục đích là để tìm số bộ ba điểm từ đầu vào sao cho một điểm là điểm giữa trên đoạn thẳng giữa 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ỳ kết hợp nào khác của A, B, C).
Chúng ta sẽ thực hiện việc này bằng cách chèn tất cả các điểm dưới dạng cặp
Hãy cùng hiểu với các ví dụ.
Đầu vào
{ 1,2 }, { 4,2} , { 2,1 } , { 7,2 } N=4 pairs Đầu ra
Count of triplet pairs that satisfy the given condition are: 1
Giải thích
Here {4,2} is mid-point between {1,2} and {7,2}. Only 1 such triplet Đầu vào
{ 1,2 }, { 4,2} , { 2,1 } , { 5,2 }, { 8,1} , {1,1} N=6 Đầu ra
Count of triplet pairs that satisfy the given condition are: 1
Giải thích
No such triplet exist
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi đang lấy một vectơ gồm các cặp kiểu
-
Mỗi cặp chứa (x, y) tọa độ.
-
Hàm mid_point (vectơ
> vec, int size) nhận một vectơ và nó có kích thước làm đầu vào và trả về số bộ ba thỏa mãn điều kiện điểm giữa. -
Lấy số lượng biến ban đầu là 0 cho các bộ ba như vậy.
-
Chèn tất cả các cặp từ vectơ vào một bộ
>. Nó sẽ có tất cả các điểm độc đáo. -
Di chuyển vectơ bằng cách sử dụng hai vòng lặp for cho mỗi cặp điểm.
-
Lưu trữ tổng tọa độ x của cả hai điểm trong số nguyên point_A và tổng tọa độ y của cả hai điểm trong số nguyên point_B.
-
Nếu cả hai tổng này trong point_A và point_B đều bằng nhau thì hãy kiểm tra điều kiện giữa điểm.
-
Nếu một cặp (point_A / 2, point_B / 2) tồn tại dưới dạng một cặp trong tập hợp có nghĩa là tồn tại điểm giữa. Số lượng tăng lên của sinh ba.
-
Cuối cùng, số lượng sẽ có số sinh ba.
-
Trả về kết quả là kết quả ở cuối vòng lặp for.
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<<"Count of triplet pairs (A, B, C) of points in 2-D space that satisfy the given condition are: "<<mid_point(vec, size);
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of triplet pairs (A, B, C) of points in 2-D space that satisfy the given condition are: 1