在 Python 中查找四个点,使它们形成一个边与 x 轴和 y 轴平行的正方形

pythonserver side programmingprogramming更新于 2025/10/10 8:12:17

假设我们有 n 对点;我们必须找到四个点,使它们能够生成一个边与 x 轴和 y 轴平行的正方形,否则返回"不可能"如果我们可以找到多个正方形,则选择面积最大的正方形。

因此,如果输入为 n = 6,points = [(2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)],则输出为 3,points 为 (2, 2) (5, 2) (2, 5) (5, 5)

为了解决这个问题,我们将遵循以下步骤 −

  • my_map := a new map

  • for i in range 0 to n, do

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

  • side := -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,则

          • 如果 (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

  • 如果 side 不等于 -1,则

    • 显示 side

    • 显示 points (x,y)、(x+side, y)、(x,y + side)、(x+side, y+side)

  • 否则,

    • 显示 "No such square"

示例

让我们看看下面的实现以便更好地理解 −

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)

相关文章


有用资源