ตรวจสอบว่าสามารถแบ่งน้ำหนักจุดด้วยเส้น 45 องศาได้หรือไม่ใน C++

โจทย์

กำหนดจุด n จุด (Xi, Yi) ในพิกัด 2D แต่ละจุดมีน้ำหนัก Wi ต้องการทราบว่าสามารถลากเส้นตรงมุม 45 องศาได้หรือไม่ ที่ทำให้น้ำหนักรวมของจุดทั้งสองข้างของเส้นเท่ากัน

ตัวอย่าง: [[-1,1,3],[-2,1,1],[1,-1,4]] → TRUE

ขั้นตอนการแก้ปัญหา

1. คำนวณ temp_x = x - y สำหรับแต่ละจุด (นี่คือการฉายจุดลงบนเส้น 45 องศา)
2. รวมน้ำหนักที่ temp_x เดียวกันไว้ใน map weight_at_x
3. สร้าง prefix sum array sum_temp จาก min_x ถึง max_x
4. ตรวจสอบว่ามีตำแหน่งไหนที่ prefix sum = total_sum - prefix sum (แบ่งครึ่งน้ำหนักได้)
5. หรือ prefix sum ก่อนหน้า = total_sum - prefix sum ปัจจุบัน

ตัวอย่างโค้ด 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[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