अवधारणा
दिए गए 'n' जोड़ी बिंदुओं के संबंध में, हमारा कार्य चार बिंदु निर्धारित करना है ताकि वे एक वर्ग बनाएं जिसकी भुजाएं x और y अक्षों के समानांतर हों या फिर "No such square" प्रदर्शित करें। यह ध्यान दिया जाना चाहिए कि यदि एक से अधिक वर्ग संभव हैं तो अधिकतम क्षेत्रफल वाले को चुनें।
इनपुट
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; // सबसे बड़ा वर्ग निर्धारित करें void findLargestSquare1(long long int points1[][2], int n1){ // मौजूद बिंदुओं को संग्रहीत करने के लिए मैप उपयोग किया जाता है map<pair<long long int, long long int>, int> m1; // उपलब्ध बिंदुओं को चिह्नित करें 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; // वर्ग के विपरीत कोनों को चुनने के लिए एक नेस्टेड लूप दिखाता है for (int i = 0; i < n1; i++) { // चुने गए बिंदु को हटाने के लिए उपयोग किया जाता है m1[make_pair(points1[i][0], points1[i][1])]--; for (int j = 0; j < n1; j++) { // चुने गए बिंदु को हटाने के लिए उपयोग किया जाता है m1[make_pair(points1[j][0], points1[j][1])]--; // सत्यापित करें कि अन्य दो बिंदु मौजूद हैं 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) { // तो यदि वर्ग सबसे बड़ा है तो इसे संग्रहीत करें 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]); } } } // हटाए गए बिंदु को जोड़ने के लिए उपयोग किया जाता है m1[make_pair(points1[j][0], points1[j][1])]++; } // हटाए गए बिंदु को जोड़ने के लिए उपयोग किया जाता है m1[make_pair(points1[i][0], points1[i][1])]++; } // सबसे बड़ा वर्ग प्रदर्शित करने के लिए उपयोग किया जाता है 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; } //ड्राइवर कोड int main(){ int n1 = 6; // दिए गए बिंदु long long int points1[n1][2]= { { 2, 2 }, { 5, 5 }, { 4, 5 }, { 5, 4 }, { 2, 5 }, { 5, 2 }}; // सबसे बड़ा वर्ग निर्धारित करें findLargestSquare1(points1, n1); return 0; }आउटपुट
Side of the square is : 3, points of the square are 2, 2 5, 2 2, 5 5, 5