45度の線で、C++で平面を2つの等しい重みの部分に分割できるかどうかを確認します

2D座標にn個の異なるポイント（Xi、Yi）があり、各ポイントの重みがWiであるとすると、45度の線を描画できるかどうかを確認する必要があります。両側のポイントの重みの合計が同じになるようにします。

したがって、入力が[[-1,1,3]、[-2,1,1]、[1、-1,4]]の場合、出力はTrue /

これを解決するには、次の手順に従います-

• n：=vのサイズ
• 1つのマップ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