检查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