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