ऐसे चार बिंदु ज्ञात कीजिए कि वे एक वर्ग बनाते हैं जिसकी भुजाएँ 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