home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

หาจุดสี่จุดเพื่อสร้างสี่เหลี่ยมจัตุรัสที่มีด้านขนานกับแกน x และ y ใน Python

สมมติว่าเรามีคะแนน n คู่ เราต้องหาจุดสี่จุดเพื่อสร้างสี่เหลี่ยมจัตุรัสที่มีด้านขนานกับแกน x และ y มิฉะนั้นจะคืนค่า "เป็นไปไม่ได้" หากเราพบมากกว่าหนึ่งช่อง ให้เลือกสี่เหลี่ยมที่มีพื้นที่สูงสุด

ดังนั้น หากอินพุตเป็น 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 ทำ

    • 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 ทำ

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

    • สำหรับ j ในช่วง 0 ถึง n ทำ

      • 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 and my_map[(points[j,0], points[i,1])]> 0 แล้ว

          • ถ้า (ด้าน <|points[i,0] - points[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]

            • 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)