TLEoj Contest #06 - Đa giác
Xem PDF
Nộp bài
Điểm:
2000 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Cho một đa giác lồi A gồm n đỉnh. Đa giác B là đa giác không tự cắt bất kì. Các đỉnh của cả hai đa giác được cho theo chiều kim đồng hồ. Mỗi đa giác không có ba điểm liên tiếp thẳng hàng.
Yêu cầu: Kiểm tra đa giác B có nằm thực sự trong đa giác A hay không? Tức là mọi điểm của B nằm trong đa giác A, không có điểm nào của B nằm trên các cạnh và đỉnh của đa giác A.
Input, Output và Subtasks
Input
- Dòng đầu tiên chứa số nguyên dương t\ (1\le t\le 200) là số bộ test.
- T nhóm dòng sau, mỗi nhóm là một bộ test, trong đó:
- Dòng đầu tiên chứa số nguyên dương n là số đỉnh của đa giác A (3\le n\le 10^5).
- N dòng tiếp theo, mỗi dòng lưu tọa độ các đỉnh của A với dòng thứ i là tọa độ của điểm x_i, y_i\ (|x_i|,|y_i|\le 10^9). Dữ liệu đảm bảo đa giác A là một đa giác lồi
- Dòng tiếp theo chứa số nguyên dương m là số đỉnh của đa giác B (3\le n\le 2\times 10^4).
- Cuối cùng là M dòng, mỗi dòng lưu tọa độ các đỉnh của B với dòng thứ i là tọa độ của điểm X_i, Y_i\ (|X_i|,|Y_i|\le 10^9).
- Chú ý: Tọa độ của các đỉnh trong đa giác có thể là 1 số thực.
Output
Gồm t dòng, mỗi dòng in kết quả test tương ứng: YES nếu đa giác B thực sự nằm trong đa giác A, và NO trong trường hợp còn lại.
Subtasks
- Subtask 1 (60\%): n\le 1000,m\le 100
- Subtask 2 (40\%): Không có ràng buộc gì thêm
Sample
Input (bàn phím)
2
6
-2 1
0 3
3 3
4 1
3 -2
2 -2
4
0 1
2 2
3 1
1 0
5
1 2
4 2
3 -3
-2 -2
-2 1
4
0 1
1 2
4 1
2 -1
Output (màn hình)
YES
NO
Bình luận