Tìm bốn điểm sao cho chúng tạo thành một hình vuông có các cạnh song song với các trục x và y trong Python

Giả sử chúng ta có n cặp điểm; chúng ta phải tìm bốn điểm để chúng có thể tạo ra một hình vuông có các cạnh song song với các trục x và y, nếu không thì trả về "không thể" Nếu chúng ta có thể tìm thấy nhiều hơn một hình vuông thì hãy chọn hình vuông có diện tích là lớn nhất.

Vì vậy, nếu đầu vào là n =6, điểm =[(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)] , thì đầu ra sẽ là 3, điểm là (2, 2) (5, 2) (2, 5) (5, 5)

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• my_map:=một bản đồ mới

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • my_map [(points [i, 0], points [i, 1])] =my_map. [(points [i, 0], points [i, 1]], 0) + 1

• bên:=-1

• x:=-1

• y:=-1

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • my_map [points [i, 0], points [i, 1]]:=my_map [points [i, 0], points [i, 1]] - 1

  • đối với j trong phạm vi từ 0 đến n, thực hiện

    • my_map [points [j, 0], points [j, 1]]:=my_map [points [j, 0], points [j, 1]] - 1

    • nếu (i không giống với j và (điểm [i, 0]-điểm [j, 0]) giống với (điểm [i, 1] - điểm [j, 1])), thì

      • nếu my_map [(điểm [i, 0], điểm [j, 1])]> 0 và my_map [(điểm [j, 0], điểm [i, 1])]> 0, thì

        • nếu (cạnh <| điểm [i, 0] - điểm [j, 0] | hoặc (cạnh giống với | điểm [i, 0] - điểm [j, 0] | và ((điểm [i, 0] * điểm [i, 0] + điểm [i, 1] * điểm [i, 1]) <(x * x + y * y)))) -

          • x:=điểm [i, 0]

          • y:=điểm [i, 1]

          • bên:=| điểm [i, 0] - điểm [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

• nếu bên không giống -1, thì

  • mặt hiển thị

  • điểm hiển thị (x, y), (x + cạnh, y), (x, y + cạnh), (x + cạnh, y + cạnh)

• nếu không,

  • hiển thị "Không có ô vuông như vậy"

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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)

Đầu vào

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

Đầu ra

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