Truy Vấn Pháo Đài Lồi
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề 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,BOUNDARYhoặcOUTSIDEtrê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
Community Discussion