找到四个点，使它们形成正方形，其边平行于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