ধরুন আমাদের 2D স্থানাঙ্কে n বিভিন্ন বিন্দু (Xi, Yi) আছে এবং প্রতিটি বিন্দুর একটি ওজন Wi আছে, আমাদের পরীক্ষা করতে হবে 45 ডিগ্রিতে একটি রেখা আঁকা যাবে কিনা। যাতে প্রতিটি পাশের বিন্দুর ওজনের যোগফল একই হবে।
সুতরাং, যদি ইনপুটটি [[-1,1,3],[-2,1,1],[1,-1,4]] এর মত হয়, তাহলে আউটপুট হবে True/
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=v এর আকার
- এক মানচিত্র ওজন_at_x সংজ্ঞায়িত করুন
- max_x :=-2000, min_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]
- সম_temp-এর শেষে সন্নিবেশ করুন (sum_temp + weight_at_x[x] এর শেষ উপাদান)
- partition_possible :=সত্য
- 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
