#134. POINTPOLY – Điểm thuộc đa giác

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Trên mặt phẳng tọa độ cho đa giác n đỉnh không tự cắt A_1A_2\ldots A_n m điểm B_1, B_2, …, B_m . Hãy xác định xem mỗi điểm B_i có thuộc đa giác hay không?

Dữ liệu vào:

  • Dòng đầu ghi hai số nguyên dương n m là số đỉnh của đa giác và số điểm cần xét;
  • n dòng tiếp theo, dòng thứ i ghi hai số nguyên x_i, y_i là hoành độ và tung độ của đỉnh A_i của đa giác;
  • m dòng tiếp theo, dòng thứ i chứa hai số nguyên dương x_i, y_i là tọa độ điểm B_i .

Dữ liệu ra:

  • Gồm m dòng, dòng thứ i ghi YES nếu điểm B_i nằm trong đa giác, ngược lại ghi NO (Chú ý: Điểm nằm trên cạnh của đa giác hoặc trùng với đỉnh của đa giác cũng được tính là nằm trong đa giác).

Ví dụ:

Dữ liệu vào:

7 3
1 0
2 2
4 1
6 3
5 6
0 6
2 4
4 3
3 2
2 1

Dữ liệu ra:

YES
YES
NO

Giới hạn:

  • 3 ≤ n ≤ 10^5; 1 ≤ m ≤ 100; |x_i|, |y_i| ≤ 10^9 .