Truy Vấn Pháo Đài Lồi

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

Một pháo đài có hình dạng đa giác lồi gồm $N$ đỉnh liệt kê theo thứ tự ngược chiều kim đồng hồ (không có $3$ đỉnh nào thẳng hàng). Có $Q$ điểm mục tiêu cần kiểm tra nhanh.

Với mỗi điểm mục tiêu, hãy xác định trong $O(\log N)$ xem điểm đó nằm bên trong (INSIDE), trên biên (BOUNDARY) hay bên ngoài (OUTSIDE) pháo đài.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$ ($3 \le N \le 10^5, 1 \le Q \le 10^5$).
  • $N$ dòng tiếp theo chứa tọa độ các đỉnh của đa giác lồi theo thứ tự ngược chiều kim đồng hồ.
  • $Q$ dòng tiếp theo chứa tọa độ các đ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 5
0 0
4 0
4 4
0 4
2 2
0 0
4 2
5 2
2 5
INSIDE
BOUNDARY
BOUNDARY
OUTSIDE
OUTSIDE
Giới hạn
  • $3 \le N, Q \le 10^5$
  • $|x|, |y| \le 10^9$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved