समस्या विवरण
मान लीजिए हमारे पास 2D निर्देशांक में n अलग-अलग बिंदु (Xi, Yi) हैं और प्रत्येक बिंदु का एक भार Wi है, हमें जांचना है कि क्या 45 डिग्री पर एक रेखा खींची जा सकती है। ताकि प्रत्येक तरफ के बिंदुओं के भार का योग समान हो।
उदाहरण
यदि इनपुट [[-1,1,3],[-2,1,1],[1,-1,4]] है, तो आउटपुट TRUE होगा।
एल्गोरिदम चरण
- n := v का आकार
- एक मैप weight_at_x परिभाषित करें
- max_x := -2000, min_x := 2000
- प्रत्येक बिंदु के लिए:
- temp_x := v[0][i] - v[1][i]
- max_x और min_x अपडेट करें
- weight_at_x[temp_x] += v[2][i]
- सरणी sum_temp बनाएं और 0 से शुरू करें
- min_x से max_x तक संचयी योग की गणना करें
- कुल योग = sum_temp का अंतिम तत्व
- जांचें कि क्या कोई विभाजन संभव है जहां दोनों तरफ का योग समान हो
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
void is_valid_part(vector<vector<int>> &v){
int n = v.size();
map<int, int> weight_at_x;
int max_x = -2000, min_x = 2000;
for (int i = 0; i < n; i++) {
int temp_x = v[0][i] - v[1][i];
max_x = max(max_x, temp_x);
min_x = min(min_x, temp_x);
weight_at_x[temp_x] += v[2][i];
}
vector<int> sum_temp;
sum_temp.push_back(0);
for (int x = min_x; x <= max_x; x++) {
sum_temp.push_back(sum_temp.back() + weight_at_x[x]);
}
int total_sum = sum_temp.back();
int partition_possible = false;
for (int i = 1; i < sum_temp.size(); i++) {
if (sum_temp[i] == total_sum - sum_temp[i])
partition_possible = true;
if (sum_temp[i - 1] == total_sum - sum_temp[i])
partition_possible = true;
}
printf(partition_possible ? "TRUE" : "FALSE");
}
int main() {
vector<vector<int>> v = {{-1,1,3},{-2,1,1},{1,-1,4}};
is_valid_part(v);
}
इनपुट
{{-1,1,3},{-2,1,1},{1,-1,4}}
आउटपुट
TRUE