C++에서 45도 선이 평면을 두 개의 동일한 무게 부분으로 나눌 수 있는지 확인하십시오.

2D 좌표에 n개의 서로 다른 점(Xi, Yi)이 있고 각 점에 가중치 Wi가 있다고 가정하면 45도에서 선을 그릴 수 있는지 확인해야 합니다. 각 면의 포인트 가중치의 합이 동일하도록 합니다.

따라서 입력이 [[-1,1,3],[-2,1,1],[1,-1,4]]와 같으면 출력은 True/

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=v의 크기
• 하나의 지도 weight_at_x 정의
• 최대_x:=-2000, 최소_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