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

n組のポイントがあるとします。辺がx軸とy軸に平行な正方形を生成できるように、4つの点を見つける必要があります。そうしないと、「不可能」と返されます。複数の正方形が見つかった場合は、面積が最大の正方形を選択してください。

したがって、入力がn =6のような場合、ポイント=[（2、2）、（5、5）、（4、5）、（5、4）、（2、5）、（5、2）] 、出力は3になり、ポイントは（2、2）（5、2）（2、5）（5、5）

これを解決するには、次の手順に従います-

• my_map：=新しいマップ

• 0からnの範囲のiの場合、実行

  • my_map [（points [i、0]、points [i、1]）] =my_map。[（points [i、0]、points [i、1]]、0）+ 1

• サイド：=-1

• x：=-1

• y：=-1

• 0からnの範囲のiの場合、実行

  • my_map [points [i、0]、points [i、1]]：=my_map [points [i、0]、points [i、1]]-1

  • 0からnの範囲のjについては、次のようにします

    • my_map [points [j、0]、points [j、1]]：=my_map [points [j、0]、points [j、1]]-1

    • （iがjと同じではなく、（points [i、0]-points [j、0]）が（points [i、1]-points [j、1]））と同じである場合、

      • my_map [（points [i、0]、points [j、1]）]>0かつmy_map[（points [j、0]、points [i、1]）]> 0の場合、

        • if（side <| points [i、0] --points [j、0] |または（sideは| points [i、0] --points [j、0] |および（（points [i、0] * points [i、0] + points [i、1] * points [i、1]）<（x * x + y * y））））−

          • x：=points [i、0]

          • y：=points [i、1]

          • side：=| points [i、0] --points [j、0] |

    • my_map [points [j、0]、points [j、1]]：=my_map [points [j、0]、points [j、1]] + 1

  • my_map [points [i、0]、points [i、1]]：=my_map [points [i、0]、points [i、1]] + 1

• サイドが-1と同じでない場合、

  • ディスプレイ側

  • 表示ポイント（x、y）、（x + side、y）、（x、y + side）、（x + side、y + side）

• それ以外の場合

  • 「そのような正方形はありません」と表示します

例

理解を深めるために、次の実装を見てみましょう-

def get_square_points(points,n):
   my_map = dict()
   for i in range(n):
      my_map[(points[i][0], points[i][1])] = my_map.get((points[i][0], points[i][1]), 0) + 1
   side = -1
   x = -1
   y = -1
   for i in range(n):
      my_map[(points[i][0], points[i][1])]-=1
      for j in range(n):
         my_map[(points[j][0], points[j][1])]-=1
            if (i != j and (points[i][0]-points[j][0]) == (points[i][1]-points[j][1])):
               if (my_map[(points[i][0], points[j][1])] > 0 and my_map[(points[j][0], points[i][1])] > 0):
                  if (side < abs(points[i][0] - points[j][0]) or (side == abs(points[i][0] - points[j][0]) and ((points[i][0] * points[i][0] + points[i][1] * points[i][1]) < (x * x + y * y)))):
                     x = points[i][0]
                     y = points[i][1]
                     side = abs(points[i][0] - points[j][0])
            my_map[(points[j][0], points[j][1])] += 1
         my_map[(points[i][0], points[i][1])] += 1
      if (side != -1):
         print("Side:", side)
         print("Points:", (x,y), (x+side, y), (x,y + side), (x+side, y+side))
      else:
         print("No such square")
n = 6
points=[(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]
get_square_points(points, n)

入力

6, [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)]

出力

Side: 3 Points: (2, 2) (5, 2) (2, 5) (5, 5)