baitap_tuan9
Điểm: 10
Vành đai tiếp tế
Mã bài: corridor · Thời gian: 2 giây · Bộ nhớ: 256 MB · Điểm: 100
Đội cứu hộ tập kết N kiện tiếp tế tại các vị trí có tọa độ nguyên (xᵢ, yᵢ). Cần căng một sợi dây khép kín bao quanh toàn bộ các kiện với tổng chiều dài nhỏ nhất. Các kiện được phép nằm bên trong hoặc trên dây.
Sợi dây gồm các đoạn thẳng nối những vị trí đặt kiện và không tự cắt. Chỉ đặt mốc tại vị trí dây đổi hướng; không đặt mốc tại điểm nằm giữa một đoạn dây thẳng.

Yêu cầu: Xác định các vị trí cần đặt mốc.
Dữ liệu vào (standard input)
• Dòng đầu chứa số nguyên N. • N dòng tiếp theo, mỗi dòng chứa hai số nguyên xᵢ, yᵢ.
Các vị trí đôi một khác nhau và không phải tất cả đều nằm trên một đường thẳng.
Dữ liệu ra (standard output)
• Dòng đầu ghi số mốc K. • K dòng tiếp theo ghi tọa độ các mốc theo thứ tự ngược chiều kim đồng hồ, bắt đầu từ mốc có hoành độ nhỏ nhất; nếu bằng nhau, chọn mốc có tung độ nhỏ nhất.
Không ghi lặp lại mốc đầu ở cuối danh sách.
Ràng buộc:
• Trong tất cả các test: 3 ≤ N ≤ 200 000; |xᵢ|, |yᵢ| ≤ 10⁸. • Có 30% số điểm: N ≤ 100. • Có 30% số điểm: N ≤ 2000. • Có 40% số điểm: không có ràng buộc bổ sung.
Ví dụ
Input
7
0 4
3 0
0 0
6 4
3 2
6 0
0 2
Output
4
0 0
6 0
6 4
0 4
Hai kiện tại (3, 0), (0, 2) nằm trên đoạn dây thẳng nên không đặt mốc. Kiện tại (3, 2) nằm bên trong.