cpp-113Đọc toàn bộ đề miễn phí
Các Lớp Bao Lồi - Thuật Toán Tách Lớp Vỏ Hành (Onion Peeling)
Cho tập hợp N điểm phân biệt trên mặt phẳng tọa độ Oxy. Quá trình tách lớp vỏ hành (Convex Layers) diễn ra như sau:
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: Monotone Chain Convex Hull, Vector Cross Product.
Nội dung đề bài
Mô tả bài toán
Cho tập hợp N điểm phân biệt trên mặt phẳng tọa độ Oxy. Quá trình tách lớp vỏ hành (Convex Layers) diễn ra như sau:
- Tìm bao lồi của tập điểm hiện tại.
- Nếu số điểm trên bao lồi ≥ 3, các điểm này tạo thành lớp thứ k (k = 1, 2, …). Ta loại bỏ các điểm này khỏi tập điểm và lặp lại bước 1.
- Quá trình dừng lại khi số điểm còn lại nhỏ hơn 3 hoặc không thể tạo thành đa giác lồi có diện tích dương.
Hãy in ra số lượng lớp bao lồi tìm được, và số lượng đỉnh của từng lớp theo thứ tự từ ngoài vào trong.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. 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àostdoutvà 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.
Input
- Dòng đầu chứa số nguyên N (3 ≤ N ≤ 2000).
- N dòng tiếp theo, mỗi dòng chứa hai số nguyên x, y (-106 ≤ x, y ≤ 106).
Output
- Dòng đầu in số nguyên K là số lớp bao lồi tách được.
- Dòng thứ hai in K số nguyên phân tách bởi dấu cách: số đỉnh thuộc lớp 1, lớp 2, ..., lớp K.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
6
0 0
4 0
4 4
0 4
1 1
2 2Output
1
4Giải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.