Kiểm tra tạo đa giác từ các cạnh cho trước (Python)

Bài toán: Cho mảng nums độ dài n cạnh. Kiểm tra có thể tạo đa giác lồi (hoặc đơn giản) từ tất cả các cạnh này không.

Điều kiện cần và đủ (Bất đẳng thức đa giác)

Sắp xếp các cạnh. Cạnh dài nhất phải nhỏ hơn tổng các cạnh còn lại.
Tức: max(nums) < sum(nums) - max(nums) ⟺ 2 * max(nums) < sum(nums).

Triển khai Python

def solve(nums):
    nums.sort()
    return nums[-1] < sum(nums[:-1])

# Test
print(solve([3, 4, 5]))       # True: 5 < 3+4=7 (tam giác)
print(solve([1, 2, 3]))       # False: 3 = 1+2 (thoái hóa thành đoạn thẳng)
print(solve([2, 2, 5]))       # False: 5 > 2+2
print(solve([4, 4, 4, 4]))    # True: 4 < 12 (tứ giác)
print(solve([1, 1, 1, 10]))   # False: 10 > 3

Kết quả

True

Giải thích

• Sắp xếp mảng, cạnh lớn nhất ở cuối nums[-1].
• Tổng các cạnh còn lại: sum(nums[:-1]).
• Điều kiện này đảm bảo có thể "khép" được đa giác.
• Độ phức tạp: O(n log n) do sort, O(1) space.