Nhật thực
Đề bài
Mô tả
Trong giờ học khoa học hôm nay, cả lớp được học về hiện tượng nhật thực. Vì đây là hiện tượng hiếm khi xảy ra và không dễ quan sát, để minh hoạ cho học sinh, thầy giáo đã viết một chương trình máy tính mô phỏng hiện tượng này.
Chương trình của thầy dùng đồ hoạ máy tính, hiển thị một mặt phẳng với hệ toạ độ . Trên màn hình, thầy vẽ hai đa giác lồi: một đa giác biểu diễn mặt trời và một đa giác biểu diễn mặt trăng. Để minh hoạ quá trình nhật thực, thầy quay đa giác mặt trăng quanh gốc toạ độ, và khi mặt trăng nằm hoàn toàn bên trong mặt trời, thầy nói đây chính là hiện tượng nhật thực!
Cả lớp rất hứng thú và lần lượt thao tác với chương trình. Chương trình cho phép học sinh thay đổi hai đa giác tuỳ ý, miễn là chúng vẫn là đa giác lồi. Tuy nhiên, không phải cặp đa giác mặt trăng và mặt trời nào cũng tạo ra được hiện tượng nhật thực.
Cho một cặp đa giác lồi biểu diễn mặt trăng và mặt trời, hãy kiểm tra xem có tồn tại một góc quay đa giác mặt trăng quanh gốc toạ độ sao cho hiện tượng nhật thực xảy ra hay không.
Gọi là tập các điểm nằm bên trong hoặc trên cạnh của đa giác . Đa giác được gọi là nằm hoàn toàn bên trong đa giác nếu . Khi quay đa giác quanh gốc toạ độ một góc , mọi điểm thuộc đều được quay quanh gốc toạ độ một góc .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu chứa số nguyên (): số đỉnh của đa giác mặt trời.
- dòng tiếp theo, dòng thứ chứa hai số nguyên (): toạ độ đỉnh thứ của đa giác mặt trời.
- Dòng tiếp theo chứa số nguyên (): số đỉnh của đa giác mặt trăng.
- dòng cuối, dòng thứ chứa hai số nguyên (): toạ độ đỉnh thứ của đa giác mặt trăng.
Dữ liệu bảo đảm:
- Cả hai đa giác đều lồi.
- Các đỉnh của mỗi đa giác được liệt kê theo chiều ngược chiều kim đồng hồ.
- Không có ba đỉnh liên tiếp nào của một đa giác thẳng hàng.
- Nếu tồn tại góc làm hiện tượng nhật thực xảy ra thì cũng tồn tại một góc sao cho mọi góc trong đoạn đều có tính chất này. Góc được đo bằng radian.
- Tổng của tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in YES nếu tồn tại góc quay đa giác mặt trăng để hiện tượng nhật thực xảy ra, ngược lại in NO.
Ràng buộc
- với mọi toạ độ
- Tổng của tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 1 9 -4 7 3 4 4 6 3 5 2 7 1 8 3 4 0 3 -1 2 0 1 1 2 3 1 1 1 -1 2 0 4 0 10 -10 0 0 -10 10 0 3 2 0 6 6 0 2 |
YES NO YES |
Bộ thứ nhất: mặt trời là tam giác ; quay tứ giác mặt trăng quanh gốc toạ độ thì có vị trí nó nằm gọn trong tam giác. Bộ thứ hai: không thể quay tam giác mặt trăng để nó nằm trong tứ giác mặt trời. Bộ thứ ba: quay mặt trăng một góc thì nó nằm trong hình vuông mặt trời; các góc cũng thoả mãn. |
| 2 3 1 1 5 1 1 5 3 0 0 1 0 0 1 4 -5 -5 5 -5 5 5 -5 5 3 0 0 3 1 1 3 |
NO YES |
Ví dụ bổ sung. Bộ thứ nhất: đỉnh của mặt trăng không đổi khi quay và nằm ngoài mặt trời. Bộ thứ hai: mặt trăng đã nằm trong mặt trời mà không cần quay. |
Bình luận