Kiểm tra xem một đường ở 45 độ có thể chia máy bay thành hai phần trọng lượng bằng nhau trong C ++ hay không

Giả sử chúng ta có n điểm khác nhau (Xi, Yi) trong tọa độ 2D và mỗi điểm có trọng số Wi, chúng ta phải kiểm tra xem có thể vẽ được một đường thẳng ở góc 45 độ hay không. Sao cho tổng trọng số của các điểm trên mỗi cạnh sẽ bằng nhau.

Vì vậy, nếu đầu vào là [[- 1,1,3], [- 2,1,1], [1, -1,4]], thì đầu ra sẽ là True /

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của v
• Xác định một bản đồ weight_at_x
• max_x:=-2000, min_x:=2000
• để khởi tạo i:=0, khi i
• temp_x:=v [0, i] - v [1, i]
• max_x:=tối đa là max_x và temp_x
• min_x:=tối thiểu là min_x và temp_x
• weight_at_x [temp_x]:=weight_at_x [temp_x] + v [2, i]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

{{-1,1,3},{-2,1,1},{1,-1,4}}

Đầu ra

TRUE