检查45度的线是否可以在C ++中将平面分为两个等重的部分

假设我们在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

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 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]

• 定义一个数组sum_temp

• 在sum_temp的末尾插入0

• 对于初始化x：= min_x，当x <= max_x时，更新（将x增加1），-

• 在sum_temp的末尾插入（sum_temp的最后一个元素+ weight_at_x [x]）

• total_sum：= sum_temp的最后一个元素

• partition_possible：=否

• 对于初始化i：= 1，当i <sum_temp的大小时，更新（将i增加1），-

• partition_possible：= true

• partition_possible：= true

• 如果sum_temp [i]与total_sum-sum_temp [i]相同，则-

• 如果sum_temp [i-1]与total_sum-sum_temp [i]相同，则-

• 返回partition_possible

例 

让我们看下面的实现以更好地理解-

#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