Kiểm tra đường thẳng 45 độ chia mặt phẳng thành hai phần bằng trọng lượng (C++)

Cho n điểm (Xi, Yi) trên mặt phẳng 2D, mỗi điểm có trọng số Wi. Xác định xem có thể vẽ một đường thẳng nghiêng 45 độ sao cho tổng trọng số hai bên đường thẳng bằng nhau hay không.

Ví dụ: Đầu vào [[-1,1,3],[-2,1,1],[1,-1,4]] → Đầu ra TRUE.

Giải thuật:

• Biến đổi tọa độ: temp_x = x - y. Đường thẳng 45 độ tương ứng với các giá trị temp_x constant.
• Gom trọng số theo temp_x vào map weight_at_x.
• Tính prefix sum trên các giá trị temp_x từ min đến max.
• Kiểm tra xem có vị trí nào chia tổng trọng số thành hai nửa bằng nhau không (kiểm tra cả tại điểm và giữa hai điểm).

Ví dụ (C++)

#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[i][0] - v[i][1];
        max_x = max(max_x, temp_x);
        min_x = min(min_x, temp_x);
        weight_at_x[temp_x] += v[i][2];
    }
    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();
    bool 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);
}

Đầu vào

{{-1,1,3},{-2,1,1},{1,-1,4}}

Đầu ra

TRUE