Python에서 측면이 x 및 y 축에 평행한 정사각형을 형성하는 네 점 찾기

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[(포인트[i,0], 포인트[i,1])] =my_map.[(포인트[i,0], 포인트[i,1]], 0) + 1

• 측면 :=-1

• x :=-1

• y :=-1

• 0에서 n 사이의 i에 대해 수행

  • my_map[포인트[i, 0], 포인트[i, 1]] :=my_map[포인트[i, 0], 포인트[i, 1]] - 1

  • 0에서 n 사이의 j에 대해 수행

    • my_map[포인트[j, 0], 포인트[j, 1]] :=my_map[포인트[j, 0], 포인트[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 (변 <|points[i,0] - 점[j,0]| 또는 (변은 |points[i,0] - points[j,0]|와 동일) 및 ((points[i,0] * 포인트[i,0] + 포인트[i,1] * 포인트[i,1]) <(x * x + y * y)))) −

          • x :=포인트[i, 0]

          • y :=포인트[i, 1]

          • 측면 :=|포인트[i,0] - 포인트[j,0]|

    • my_map[포인트[j, 0], 포인트[j, 1]] :=my_map[포인트[j, 0], 포인트[j, 1]] + 1

  • my_map[포인트[i, 0], 포인트[i, 1]] :=my_map[포인트[i, 0], 포인트[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)