C++で辺がx軸とy軸に平行な正方形を形成するように4つの点を見つけます

コンセプト

与えられた「n」点のペアに関して、私たちのタスクは、辺がx軸とy軸に平行な正方形を形成するように、または「そのような正方形はありません」と表示されるように4つの点を決定することです。複数の正方形が可能な場合は、最大の面積を持つ正方形を選択することに注意してください。

入力

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

メソッド

簡単な方法 − 4つのネストされたループを持つすべての可能なポイントのペアを選択し、ポイントが主軸に平行な正方形を形成するかどうかを確認します。はいの場合は、それが面積の点でこれまでで最大の正方形であるかどうかを確認し、結果を保存してから、プログラムの最後に結果を印刷することがわかっています。

時間計算量-O（N ^ 4）

効率的な方法 −正方形の右上隅と左下隅にネストされたループを作成し、これら2つのポイントで正方形を生成してから、想定された他の2つのポイントが実際に存在するかどうかを確認します。ここで、ポイントが存在するかどうかを確認するには、マップを作成してポイントをマップに保存し、ポイントが存在するかどうかを確認する時間を短縮します。さらに、これまでの面積で最大の正方形をチェックして、最後に表示します。

例

// 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