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

ऐसे चार बिंदु ज्ञात कीजिए कि वे एक वर्ग बनाते हैं जिसकी भुजाएँ C++ में x और y अक्षों के समानांतर हैं

अवधारणा

दिए गए 'n' युग्मों के संबंध में, हमारा कार्य चार बिंदुओं को निर्धारित करना है ताकि वे एक वर्ग का निर्माण करें जिसकी भुजाएँ x और y अक्षों के समानांतर हों या फिर "ऐसा कोई वर्ग नहीं" प्रदर्शित करें। यह ध्यान दिया जाना चाहिए कि यदि एक से अधिक वर्ग संभव हो तो अधिकतम क्षेत्रफल वाला वर्ग चुनें।

इनपुट

n = 6, points = (2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)

आउटपुट

Side of the square is: 3,
points of the square are 2, 2 5, 2 2, 5 5, 5

स्पष्टीकरण

अंक 2, 2 5, 2 2, 5 5, 5 भुजा 3 का एक वर्ग बनाते हैं

इनपुट

n= 6, points= (2, 2), (5, 6), (4, 5), (5, 4), (8, 5), (4, 2)

आउटपुट

No such square

विधि

सरल विधि - चार नेस्टेड लूप वाले बिंदुओं के सभी संभावित युग्मों का चयन करें और फिर सत्यापित करें कि क्या बिंदु एक वर्ग बनाते हैं जो मुख्य अक्षों के समानांतर है। यह देखा गया है कि यदि हाँ, तो सत्यापित करें कि क्या यह क्षेत्रफल की दृष्टि से अब तक का सबसे बड़ा वर्ग है और परिणाम को संग्रहीत करें, और फिर कार्यक्रम के अंत में परिणाम प्रिंट करें।

समय जटिलता - O(N^4)

कुशल विधि - वर्ग के ऊपरी दाएं और निचले बाएं कोने के लिए एक नेस्टेड लूप बनाएं और उन दो बिंदुओं के साथ एक वर्ग उत्पन्न करें, फिर सत्यापित करें कि क्या अन्य दो बिंदु जो वास्तव में मौजूद थे। अब यह सत्यापित करने के लिए कि कोई बिंदु मौजूद है या नहीं, एक नक्शा बनाएं और बिंदुओं को मानचित्र में संग्रहीत करें ताकि यह सत्यापित किया जा सके कि बिंदु मौजूद हैं या नहीं। इसके अलावा, क्षेत्र के अनुसार अब तक के सबसे बड़े वर्ग की जांच करें और अंत में इसे प्रदर्शित करें।

उदाहरण

// C++ implemenataion of the above approach
#include <bits/stdc++.h>
using namespace std;
// Determine the largest square
void findLargestSquare1(long long int points1[][2], int n1){
   // Used to map to store which points exist
   map<pair<long long int, long long int>, int> m1;
   // mark the available points
   for (int i = 0; i < n1; i++) {
      m1[make_pair(points1[i][0], points1[i][1])]++;
   }
   long long int side1 = -1, x1 = -1, y1 = -1;
   // Shows a nested loop to choose the opposite corners of square
   for (int i = 0; i < n1; i++) {
      // Used to remove the chosen point
      m1[make_pair(points1[i][0], points1[i][1])]--;
      for (int j = 0; j < n1; j++) {
         // Used to remove the chosen point
         m1[make_pair(points1[j][0], points1[j][1])]--;
         // Verify if the other two points exist
      if (i != j && (points1[i][0]-points1[j][0]) == (points1[i][1]-points1[j][1])){
         if (m1[make_pair(points1[i][0], points1[j][1])] > 0
            && m1[make_pair(points1[j][0], points1[i][1])] > 0) {
            // So if the square is largest then store it
         if (side1 < abs(points1[i][0] - points1[j][0])
            || (side1 == abs(points1[i][0] -points1[j][0])
            && ((points1[i][0] * points1[i][0]+ points1[i][1] * points1[i][1])
            < (x1 * x1 + y1 * y1)))) {
               x1 = points1[i][0];
               y1 = points1[i][1];
               side1 = abs(points1[i][0] - points1[j][0]);
            }
         }
      }
      // Used to add the removed point
      m1[make_pair(points1[j][0], points1[j][1])]++;
   }
   // Used to add the removed point
   m1[make_pair(points1[i][0], points1[i][1])]++;
}
// Used to display the largest square
if (side1 != -1)
   cout << "Side of the square is : " << side1
   << ", \npoints of the square are " << x1 << ", " << y1<< " "<< (x1 + side1) << ", " << y1
   << " "
   << (x1) << ", " << (y1 + side1)
   << " "
   << (x1 + side1) << ", " << (y1 + side1) << endl;
   else
   cout << "No such square" << endl;
}
//Driver code
int main(){
   int n1 = 6;
   // given points
   long long int points1[n1][2]= { { 2, 2 }, { 5, 5 }, { 4, 5 }, { 5, 4 }, { 2, 5 }, { 5, 2 }};
   // Determine the largest square
   findLargestSquare1(points1, n1);
   return 0;
}

आउटपुट

Side of the square is : 3,
points of the square are 2, 2 5, 2 2, 5 5, 5

  1. ऐसी संख्या x ज्ञात कीजिए कि C++ में x और उसके अंकों का योग दिए गए n के बराबर हो

    यहां हम एक समस्या देखेंगे, जहां हम एक संख्या n लेते हैं, हमें एक और मान x ज्ञात करना होता है, जैसे कि x का x + अंकों का योग दी गई संख्या n के समान हो। मान लीजिए n का मान 21 है। यह प्रोग्राम एक संख्या x =15, 15 + अंकों का योग 15, यानी 15 + 1 + 5 =21 =n के रूप में लौटाएगा। इस समस्या को हल करने के लिए

  1. ऐसी दो संख्याएँ ज्ञात कीजिए जिनका योग और GCD C++ में दिया गया है

    हमारे पास दो संख्याओं a और b का योग और gcd है। हमें a और b दोनों संख्याएँ ज्ञात करनी हैं। यदि यह संभव नहीं है, तो वापसी -1। मान लीजिए कि योग 6 है और gcd 2 है, तो संख्याएँ 4 और 2 हैं। दृष्टिकोण ऐसा है, जैसा कि GCD दिया जाता है, तो ज्ञात होता है कि संख्याएँ इसके गुणज होंगी। अब निम्नलिखित चरण हैं य

  1. चार बिंदु खोजें जैसे कि वे एक वर्ग बनाते हैं जिसकी भुजाएँ पायथन में x और y कुल्हाड़ियों के समानांतर होती हैं

    मान लीजिए कि हमारे पास n अंक हैं; हमें चार बिंदु खोजने होंगे ताकि वे एक वर्ग उत्पन्न कर सकें जिसकी भुजाएँ x और y कुल्हाड़ियों के समानांतर हों अन्यथा संभव नहीं लौटते हैं यदि हम एक से अधिक वर्ग पा सकते हैं तो वह चुनें जिसका क्षेत्रफल अधिकतम है। इसलिए, यदि इनपुट n =6 की तरह है, तो अंक =[(2, 2), (5, 5)