Bao lồi tập điểm: Thuật toán Chuỗi đơn điệu Andrew Monotone Chain

Mục tiêu kiến thức

• Hiểu định nghĩa bao lồi (Convex Hull) của tập điểm trên mặt phẳng 2D.
• Cài đặt thuật toán Andrew's Monotone Chain với độ phức tạp O(N log N) thông qua sắp xếp tọa độ và tích có hướng (cross product).
• Xử lý các điểm thẳng hàng (collinear points) và xuất thứ tự ngược chiều kim đồng hồ bắt đầu từ điểm có tọa độ x nhỏ nhất.

Mô tả bài toán

Cho N điểm trên mặt phẳng 2D. Hãy tìm tập các đỉnh của bao lồi đa giác chứa toàn bộ N điểm này. Nếu có nhiều điểm thẳng hàng trên cạnh của bao lồi, chỉ giữ lại các điểm ở hai đầu mút (không chứa điểm strictly inside cạnh).

In ra số lượng đỉnh của bao lồi, và tọa độ các đỉnh theo thứ tự ngược chiều kim đồng hồ (counter-clockwise) bắt đầu từ điểm có x nhỏ nhất (nếu trùng x, chọn y nhỏ nhất).

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 3 ≤ N ≤ 10⁵.
• -10⁹ ≤ X_i, Y_i ≤ 10⁹.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.