数据结构
网络
关系数据库管理系统 (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+ 次浏览
广告