Chu vi bao lồi

Hướng tiếp cận

Tính bao lồi của $N$ điểm rồi cộng độ dài các cạnh của bao lồi đó (Euclid).

Thuật toán chuẩn: Andrew monotone chain (quét theo $x$ rồi quét ngược). Khử trùng điểm trước, ta lần lượt dựng nửa dưới và nửa trên của bao bằng stack với điều kiện cross product.

Nhận xét quan trọng

1. Khử trùng điểm bằng sort + unique, nếu sau khử chỉ còn 1 điểm thì chu vi $=0$.
2. Trường hợp suy biến — tất cả thẳng hàng: bao lồi suy biến thành đoạn thẳng. Chu vi $=2·d$ với $d$ là khoảng cách giữa hai điểm xa nhau nhất.
3. Trong Andrew, dùng cross(O,A,B) <= 0 (so sánh nhỏ-hơn-hoặc-bằng) sẽ loại luôn các điểm thẳng hàng trên cạnh.
4. Phần cross dùng long long (đến $2·{10}^{12}$); chỉ cộng độ dài cạnh mới dùng double (hoặc long double).

Thuật toán (Andrew monotone chain)

sort các điểm theo (x, y) tăng dần và khử trùng
nếu chỉ còn 1 điểm → in 0
nửa dưới L:
    for p in pts:
        while |L| ≥ 2 and cross(L[-2], L[-1], p) ≤ 0:
            pop L
        append p to L
nửa trên U: lặp tương tự, đảo chiều pts
hull = L[:-1] + U[:-1]
per = Σ Euclid distance giữa các đỉnh kề trên hull

Độ phức tạp

• Thời gian: $O(N\log N)$ (sort + 2 lượt quét tuyến tính).
• Bộ nhớ: $O(N)$.

Lưu ý cài đặt

• Tránh Jarvis march (gift-wrapping) $O(N·H)$: khi $H=\Theta (N)$ (ví dụ điểm trên đường tròn), nó thành $O(N^2)$ và TLE với $N={10}^5$.
• In ra với 6 chữ số sau dấu phẩy; sai số ${10}^{-4}$ được chấp nhận.