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

C++ में वृत्त के अंदर स्थित बिंदुओं की गणना के लिए क्वेरीज़


समस्या विवरण

इस समस्या में, हमें एक 2D तल पर n बिंदु दिए गए हैं, जिनमें से प्रत्येक के निर्देशांक (x, y) हैं। हमारा कार्य क्वेरीज़ को हल करना है। प्रत्येक क्वेरी के लिए, हमें एक पूर्णांक R दिया जाता है। हमें उन बिंदुओं की संख्या ज्ञात करनी है जो मूल बिंदु (0, 0) को केंद्र और त्रिज्या R वाले वृत्त के अंदर स्थित हैं।

उदाहरण

इनपुट

n = 4
बिंदु: (2, 1), (1, 2), (3, 3), (-1, 0), (-2, -2)
क्वेरी 1: R = 2

आउटपुट

1

व्याख्या - क्वेरी के लिए त्रिज्या 2 है, बिंदु (-1, 0) वृत्त के अंदर स्थित है, जबकि अन्य सभी बिंदु बाहर हैं।

मूल बिंदु (0,0) को केंद्र वाले वृत्त का गणितीय समीकरण है: x² + y² ≤ r²। इसलिए, एक बिंदु (x, y) वृत्त के अंदर स्थित होगा यदि x² + y² ≤ r² संतुष्ट होता है।

सरल दृष्टिकोण

इस समस्या को हल करने का एक सरल तरीका है प्रत्येक क्वेरी के लिए सभी बिंदुओं को पार करना और सूत्र का उपयोग करके जांचना कि क्या वे वृत्त की परिधि के अंदर स्थित हैं या नहीं।

कार्यक्रम उदाहरण

#include <iostream>
using namespace std;

int solveQuery(int x[], int y[], int n, int R) {
    int count = 0;
    for(int i = 0; i < n; i++) {
        if(((x[i]*x[i]) + (y[i]*y[i])) <= (R*R))
            count++;
    }
    return count;
}

int main() {
    int x[] = { 2, 1, 3, -1, -2 };
    int y[] = { 1, 2, 3, 0, -2 };
    int n = sizeof(x) / sizeof(x[0]);
    int Q = 2;
    int query[] = {4, 2 };
    for(int i = 0; i < Q; i++)
        cout << "क्वेरी " << (i+1) << ": वृत्त के अंदर स्थित बिंदुओं की संख्या " << solveQuery(x, y, n, query[i]) << "\n";
    return 0;
}

आउटपुट

क्वेरी 1: वृत्त के अंदर स्थित बिंदुओं की संख्या 4
क्वेरी 2: वृत्त के अंदर स्थित बिंदुओं की संख्या 1

इस दृष्टिकोण का उपयोग करके समाधान की समय जटिलता O(n*Q) होगी। क्योंकि प्रत्येक क्वेरी के लिए, हम सभी n बिंदुओं के लिए x² + y² का मान गणना करेंगे।

कुशल समाधान

एक कुशल समाधान यह होगा कि हम सभी n बिंदुओं के लिए x² + y² के मान की पूर्व-गणना (precompute) करें और इसे एक सरणी में संग्रहीत करें जिसका उपयोग सभी क्वेरीज़ के लिए किया जा सके। और फिर प्रत्येक क्वेरी के लिए समाधान खोजें। प्रोग्राम को और अनुकूलित करने के लिए, हम सरणी को क्रमबद्ध (sort) कर सकते हैं और फिर उस पहले तत्व को ढूंढ सकते हैं जो वृत्त के बाहर स्थित है। इससे समय कम लगेगा।

कार्यक्रम उदाहरण

#include <bits/stdc++.h>
using namespace std;

int solveQuery(int points[], int n, int rad) {
    int l = 0, r = n - 1;
    while ((r - l) > 1) {
        int mid = (l + r) / 2;
        if (points[mid] > (rad * rad))
            r = mid - 1;
        else
            l = mid;
    }
    if ((sqrt(points[l])) > (rad * 1.0))
        return 0;
    else if ((sqrt(points[r])) <= (rad * 1.0))
        return r + 1;
    else
        return l + 1;
}

int main() {
    int n = 5;
    int point[n][2] = { {2, 1}, {1, 2}, {3, 3}, {-1, 0}, {-2, -2} };
    int Q = 2;
    int query[] = {4, 2 };
    int points[n];
    // मानों की पूर्व-गणना
    for (int i = 0; i < n; i++)
        points[i] = ( point[i][0]*point[i][0] ) + ( point[i][1]*point[i][1] );
    sort(points, points + n);
    for(int i = 0; i < Q; i++)
        cout << "क्वेरी " << (i+1) << ": वृत्त के अंदर स्थित बिंदुओं की संख्या " 
            << solveQuery(points, n, query[i]) << "\n";
    return 0;
}

आउटपुट

क्वेरी 1: वृत्त के अंदर स्थित बिंदुओं की संख्या 4
क्वेरी 2: वृत्त के अंदर स्थित बिंदुओं की संख्या 1
  1. C++ में वृत्त और आयत के ओवरलैप की जांच C++ में वृत्त और आयत के ओवरलैप की जांच

    मान लीजिए हमारे पास एक वृत्त है जिसे (त्रिज्या, xc, yc) से दर्शाया जाता है, जहां (xc, yc) केंद्र के निर्देशांक हैं। हमारे पास एक अक्ष-संरेखित आयत भी है जिसे (x1, y1, x2, y2) से दर्शाया जाता है, जहां (x1, y1) निचले-बाएं कोने के निर्देशांक हैं और (x2, y2) ऊपरी-दाएं कोने के निर्देशांक हैं। हमें जांचना

  1. C++ में तल में समानांतर चतुर्भुजों की गणना C++ में तल में समानांतर चतुर्भुजों की गणना

    हमें एक तल दिया गया है जिसमें समानांतर चतुर्भुज बनाने वाले बिंदु हैं और कार्य दिए गए बिंदुओं का उपयोग करके बनने वाले समानांतर चतुर्भुजों की संख्या की गणना करना है। समानांतर चतुर्भुज में एक चतुर्भुज की विपरीत भुजाएँ समानांतर होती हैं और इसलिए विपरीत कोण समान होते हैं। इनपुट - int a[] = {0, 2, 5, 5,

  1. C++ में एक रेखा पर अधिकतम बिंदु C++ में एक रेखा पर अधिकतम बिंदु

    मान लीजिए हमारे पास एक 2D तल है। हमें उन अधिकतम बिंदुओं की संख्या ढूंढनी है जो एक ही सीधी रेखा पर स्थित हैं। तो यदि बिंदु इस तरह हैं -तो 4 बिंदु हैंइसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -n := बिंदुओं की संख्या, यदि n < 3, तो n लौटाएंans := 2i को 1 से n - 1 तक की रेंज मेंcount := 0इं