Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में जांचें कि 45 डिग्री पर एक रेखा तल को दो समान भार वाले भागों में विभाजित कर सकती है या नहीं

समस्या विवरण

मान लीजिए हमारे पास 2D निर्देशांक में n अलग-अलग बिंदु (Xi, Yi) हैं और प्रत्येक बिंदु का एक भार Wi है, हमें जांचना है कि क्या 45 डिग्री पर एक रेखा खींची जा सकती है। ताकि प्रत्येक तरफ के बिंदुओं के भार का योग समान हो।

उदाहरण

यदि इनपुट [[-1,1,3],[-2,1,1],[1,-1,4]] है, तो आउटपुट TRUE होगा।

एल्गोरिदम चरण

  • n := v का आकार
  • एक मैप weight_at_x परिभाषित करें
  • max_x := -2000, min_x := 2000
  • प्रत्येक बिंदु के लिए:
    • temp_x := v[0][i] - v[1][i]
    • max_x और min_x अपडेट करें
    • weight_at_x[temp_x] += v[2][i]
  • सरणी sum_temp बनाएं और 0 से शुरू करें
  • min_x से max_x तक संचयी योग की गणना करें
  • कुल योग = sum_temp का अंतिम तत्व
  • जांचें कि क्या कोई विभाजन संभव है जहां दोनों तरफ का योग समान हो

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
  1. C++ में रेखा वृत्त को स्पर्श करती है, प्रतिच्छेद करती है या बाहर है जांचें C++ में रेखा वृत्त को स्पर्श करती है, प्रतिच्छेद करती है या बाहर है जांचें

    समस्या विवरण एक वृत्त (केंद्र h,k और त्रिज्या r) और रेखा (ax+by+c=0) दी गई है। जांचें कि रेखा वृत्त को स्पर्श करती है, प्रतिच्छेद करती है, या बाहर है। विधि केंद्र से रेखा की लंबवत दूरी P निकालें: P = |ah + bk + c| / √(a²+b²) P की त्रिज्या r से तुलना करें: r → बाहर P = r → स्पर्श करती है

  1. - C++ में दी गई शर्तों के अनुसार सरणी को समान योग भागों में विभाजित करें

    यहां हम एक समस्या देखेंगे। मान लीजिए एक सरणी arr दी गई है। हमें जांचना है कि क्या सरणी को दो भागों में विभाजित किया जा सकता है, जैसे कि: दोनों सब-एरेज का योग समान होगा सभी एलिमेंट्स जो 5 के गुणक हैं, एक ही समूह में होंगे सभी एलिमेंट्स जो 3 के गुणक हैं लेकिन 5 के नहीं, एक ही समूह में होंगे बाकी सभी

  1. - C++ में जांचें कि क्या रेखा मूल बिंदु से गुजरती है

    इस खंड में हम देखेंगे कि कैसे जांचें कि कोई रेखा खंड मूल बिंदु से गुजरता है या नहीं। हमारे पास रेखा खंड के अंतिम बिंदुओं को दर्शाने के लिए दो निर्देशांक बिंदु हैं। दृष्टिकोण सरल है। यदि हम सीधी रेखा का समीकरण बना सकते हैं, और समीकरण में (0, 0) रखकर, समीकरण संतुष्ट होता है, तो रेखा मूल बिंदु से गुजर