ICPC 2021 miền Trung - E: Convex Quadrilateral

Xem dạng PDF
Gửi bài giải
Điểm: 0,50
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
ICPC 2021 miền Trung
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Lưu ý: Sử dụng giới hạn thời gian/bộ nhớ ở trang web OJ thay vì giới hạn trong đề.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    YougiTuber  đã bình luận lúc 18, Tháng 10, 2025, 14:44

    Spoil⚠️

    (Các điểm không được xếp theo thứ tự ccw/cw)

    Cách ~1~: Kiểm tra có một điểm nằm trong tam giác tạo bởi ~3~ điểm còn lại không

    Xét ~4~ trường hợp, giả sử ~4~ điểm là ~A~, ~B~, ~C~, ~D~. Muốn kiểm tra ~D~ có thuộc tam giác ~ABC~ không ta check bằng diện tích. ~S_{ABC} = S_{ABD} + S_{ACD} + S_{BCD}~

    Nếu ~D~ thuộc tam giác ~ABC~ thì không tạo thành được đa giác lồi.

    Cách ~2~: Tìm bao lồi

    Dùng phiên bản tìm bao lồi, không giữ lại các điểm thẳng hàng trên cạnh, nếu bao lồi đủ ~4~ điểm, thì tạo được đa giác lồi