Chương trình sắp xếp tập điểm Descartes theo góc cực trong Python

Cho tập điểm Descartes points. Sắp xếp theo góc cực (polar angle) trong khoảng [0, 2π). Nếu góc bằng nhau, sắp xếp theo khoảng cách đến gốc tăng dần.

Ví dụ: points = [(1,1), (1,-2), (-2,2), (5,4), (4,5), (2,3), (-3,4)] → kết quả [(5,4), (1,1), (4,5), (2,3), (-3,4), (-2,2), (1,-2)].

Thuật toán giải quyết

1. Định nghĩa hàm key cho sorted():
   • Tính atan = atan2(y, x) (góc trong [-π, π])
   • Nếu atan >= 0: khóa = (atan, x²+y²)
   • Ngược lại: khóa = (2π + atan, x²+y²) (chuyển góc âm sang [π, 2π))
2. Sắp xếp points theo khóa trên

Ví dụ minh họa

import math

def solve(points):
    def key(x):
        atan = math.atan2(x[1], x[0])
        return (atan, x[1]**2 + x[0]**2) if atan >= 0 else (2*math.pi + atan, x[0]**2 + x[1]**2)
    return sorted(points, key=key)

points = [(1,1), (1,-2), (-2,2), (5,4), (4,5), (2,3), (-3,4)]
print(solve(points))

Đầu vào

[(1,1), (1,-2),(-2,2),(5,4),(4,5),(2,3),(-3,4)]

Đầu ra

[(5, 4), (1, 1), (4, 5), (2, 3), (-3, 4), (-2, 2), (1, -2)]