資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在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
更新於：2020年7月24日
1K+ 次瀏覽
廣告