মান লিজিয়ে nটি আলাদা পয়েন্ট (Xi, Yi) ২D কোঅর্ডিনেটে আছে এবং প্রতিটি পয়েন্টের ওজন Wi। আমাদের যাচাই করতে হবে ৪৫ ডিগ্রির একটি রেখা আঁকা যায় কিনা যাতে রেখার দুপাশের পয়েন্টগুলোর ওজন যোগফল সমান হয়।
ইনপুট: [[-1,1,3],[-2,1,1],[1,-1,4]] হলে আউটপুট: True
সমাধানের ধাপগুলো:
- n := v.size()
- weight_at_x ম্যাপ সংজ্ঞায়িত করুন
- max_x := -2000, min_x := 2000
- i=0 থেকে n-1 পর্যন্ত: temp_x = v[0][i] - v[1][i], max_x/min_x আপডেট করুন, weight_at_x[temp_x] += v[2][i]
- sum_temp অ্যারে তৈরি করুন, ০ পুশ করুন
- x=min_x থেকে max_x পর্যন্ত: sum_temp-এ sum_temp.back() + weight_at_x[x] পুশ করুন
- total_sum := sum_temp.back()
- partition_possible := false
- i=1 থেকে sum_temp.size()-1 পর্যন্ত: যদি sum_temp[i] == total_sum - sum_temp[i] বা sum_temp[i-1] == total_sum - sum_temp[i], partition_possible = true
- 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
