পাইথন প্রোগ্রাম - পয়েন্টগুলোর কনভেক্স হাল গঠন করে কিনা তা যাচাই করুন

মনে করুন একটি পলিগনের বাহিরের পয়েন্টগুলো ঘড়ির কাঁটার দিকে অর্ডার্ড আছে। এগুলো কনভেক্স হাল গঠন করে কিনা তা যাচাই করতে হবে।

ইনপুট points = [(3,4), (4,7), (7,8), (11,6), (12,3), (10,1), (5,2)] হলে আউটপুট হবে True।

সমাধানের ধাপসমূহ:

• n := points-এর আকার
• i = 0 থেকে points-এর আকার পর্যন্ত:
  • p1 := points[i-2] যদি i > 1, অন্যথায় points[n-2]
  • p2 := points[i-1] যদি i > 0, অন্যথায় points[n-1]
  • p3 := points[i]
  • যদি (p1, p2, p3) পয়েন্টগুলোর কোণ > 180: False ফেরত দিন
• True ফেরত দিন

উদাহরণ

বাস্তবায়ন:

import math

def get_angle(a, b, c):
    angle = math.degrees(math.atan2(c[1]-b[1], c[0]-b[0]) - math.atan2(a[1]-b[1], a[0]-b[0]))
    return angle + 360 if angle < 0 else angle

def solve(points):
    n = len(points)
    for i in range(len(points)):
        p1 = points[i-2]
        p2 = points[i-1]
        p3 = points[i]
        if get_angle(p1, p2, p3) > 180:
            return False
    return True

points = [(3,4), (4,7), (7,8), (11,6), (12,3), (10,1), (5,2)]
print(solve(points))

ইনপুট

[(3,4), (4,7), (7,8), (11,6), (12,3), (10,1), (5,2)]

আউটপুট

True