जांचें कि क्या 45 डिग्री पर एक रेखा विमान को दो बराबर वजन भागों में C++ . में विभाजित कर सकती है

मान लीजिए कि हमारे पास 2D निर्देशांक में n अलग-अलग बिंदु (Xi, Yi) हैं और प्रत्येक बिंदु का वजन Wi है, हमें जांचना है कि क्या 45 डिग्री पर एक रेखा खींची जा सकती है। ताकि दोनों तरफ के बिंदुओं के भार का योग समान हो।

इसलिए, यदि इनपुट [[-1,1,3], [-2,1,1], [1,-1,4]] जैसा है, तो आउटपुट सही होगा/

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=v का आकार
• एक मानचित्र weight_at_x परिभाषित करें
• max_x:=-2000, min_x:=2000
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• temp_x :=v[0, i] - v[1, i]
• max_x :=max_x और temp_x की अधिकतम
• min_x :=न्यूनतम min_x और temp_x
• weight_at_x[temp_x] :=weight_at_x[temp_x] + v[2, i]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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