Đường cao tốc Cần Thơ
Đề bài
Mô tả
Chủ tịch thành phố Cần Thơ đang lên kế hoạch xây một đường cao tốc mới. Đường cao tốc sẽ nối Cần Thơ với Thành phố Hồ Chí Minh, mang lại thịnh vượng cho cả vùng.
Tất nhiên, đường cao tốc không được cắt qua điểm du lịch nổi tiếng của Cần Thơ là chợ nổi Cái Răng, vốn không thể di dời. Nhiệm vụ của bạn là kiểm tra xem đường cao tốc mới có cắt qua chợ nổi Cái Răng hay không.
Cụ thể hơn, đường cao tốc được biểu diễn bởi hai đường thẳng song song và : phần mặt phẳng nằm giữa hai đường thẳng này là đường cao tốc. Chợ nổi Cái Răng được biểu diễn gần đúng bởi một đa giác lồi có không quá đỉnh. Hãy kiểm tra xem đường cao tốc và chợ nổi có phần chung với diện tích dương hay không.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên : số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm hai dòng:
- Dòng thứ nhất chứa bốn số nguyên , , , .
- Dòng thứ hai chứa số nguyên : số đỉnh của đa giác lồi biểu diễn chợ nổi, tiếp theo là số nguyên : tọa độ các đỉnh của đa giác. Các đỉnh được liệt kê theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng chứa YES nếu đường cao tốc và chợ nổi có phần chung với diện tích dương, ngược lại in ra NO.
Ràng buộc
- .
- , , .
- .
- .
- Trong mỗi đa giác, không có hai đỉnh trùng tọa độ và không có ba đỉnh liên tiếp thẳng hàng.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 0 1 0 1 6 2 2 1 3 1 4 2 5 3 4 3 3 0 1 0 1 6 2 -1 1 0 1 1 2 2 3 1 3 0 |
NO YES |
Đường cao tốc là dải . Ở bộ thứ nhất, mọi đỉnh của đa giác có nên đa giác nằm hẳn phía trên dải. Ở bộ thứ hai, đa giác trải từ đến , phần nằm trong dải có diện tích dương. |
| 2 1 0 0 2 3 2 0 4 0 3 5 1 1 -5 5 4 -10 -10 10 -10 10 10 -10 10 |
NO YES |
Ở bộ thứ nhất, dải là và tam giác nằm trong : hai hình chỉ chạm nhau tại đỉnh , diện tích chung bằng . Ở bộ thứ hai, dải đi qua giữa hình vuông. |
Bình luận