Olympic Sinh Viên 2019 - Siêu cúp - Cắt bánh
Xem dạng PDF
Gửi bài giải
Điểm:
1,10 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Bình luận
💡 Gợi ý hướng làm (GATEAU)
! Đây là bài hình học tính toán dạng trích xuất mặt (face extraction) từ đồ thị phẳng. ! ! 1. Xử lý tọa độ ! Vì các đường chỉ theo 8 hướng, giao điểm có thể là số .5 → nên nhân đôi toàn bộ tọa độ để dùng số nguyên (tránh sai số double). ! ! 2. Xây dựng đồ thị ! - Đỉnh: các giao điểm + góc + đầu mút ! - Cạnh: các đoạn giữa các đỉnh kề nhau ! - Chỉ giữ giao điểm nằm trên đoạn (không lấy giao của đường kéo dài) để tránh TLE ! - Nên dùng sort + unique + binary search thay vì map ! ! 3. Xử lý thành phần rời rạc ! Nếu có phần không chạm biên → cần nối lại (có thể dùng BFS + ray casting để thêm cạnh ảo) ! ! 4. Duyệt các mặt ! - Sắp xếp cạnh kề theo góc ! - Đi theo quy tắc “rẽ phải nhất” (theo CCW) ! - Tính diện tích bằng Shoelace ! - Chỉ lấy các mặt có diện tích dương ! ! 5. Kết quả ! Nhớ chia lại diện tích cho phù hợp do đã scale tọa độ ! ! 👉 Cuối cùng sort và in ra