Vị Trí Của Kẻ Du Hành

Buổi 61 — Hình học tính toán
Points
26
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Một vùng lãnh thổ được mô tả bằng một đa giác đơn gồm $N$ đỉnh (có thể lõm). Có $Q$ điểm đánh dấu vị trí của các kẻ du hành.

Sử dụng thuật toán bắn tia (Ray Casting), hãy xác định với mỗi kẻ du hành xem họ đang ở bên trong (INSIDE), nằm trên biên (BOUNDARY), hay ở bên ngoài (OUTSIDE) vùng lãnh thổ.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$ ($3 \le N \le 1000, 1 \le Q \le 1000$).
  • $N$ dòng tiếp theo chứa tọa độ các đỉnh của đa giác theo thứ tự dọc theo chu vi.
  • $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x, y$ là tọa độ một điểm truy vấn.
Dữ liệu ra
  • Với mỗi truy vấn, in ra INSIDE, BOUNDARY hoặc OUTSIDE trên một dòng.
Ví dụ
Input Output
4 4
0 0
4 0
4 4
0 4
2 2
4 2
5 2
0 0
INSIDE
BOUNDARY
OUTSIDE
BOUNDARY
Giới hạn
  • $3 \le N \le 1000$, $1 \le Q \le 1000$
  • $|x|, |y| \le 10^9$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved