Kiểm tra điểm nằm trong đa giác bất kỳ (Winding Number / Ray Casting)

Mô tả bài toán

Cho một đa giác đơn (không tự cắt, không nhất thiết lồi) gồm N đỉnh P₀, P₁, …, P_N-1.

Bạn cần trả lời Q truy vấn. Mỗi truy vấn gồm một điểm M(x, y).

Yêu cầu: Xác định vị trí tương đối của điểm M đối với đa giác:

• In BOUNDARY nếu M nằm trên cạnh hoặc đỉnh của đa giác.
• In INSIDE nếu M nằm nghiêm ngặt bên trong đa giác.
• In OUTSIDE nếu M nằm bên ngoài đa giác.

Dữ liệu vào

• Dòng đầu chứa số nguyên N (3 ≤ N ≤ 1000).
• N dòng tiếp theo, mỗi dòng gồm hai số nguyên x, y là tọa độ các đỉnh của đa giác theo thứ tự liên tiếp (-10⁶ ≤ x, y ≤ 10⁶).
• Dòng tiếp theo chứa số nguyên Q (1 ≤ Q ≤ 1000).
• Q dòng tiếp theo, mỗi dòng chứa hai số nguyên x, y là tọa độ điểm truy vấn (-10⁶ ≤ x, y ≤ 10⁶).

Dữ liệu ra

• Với mỗi truy vấn, in ra kết quả trên một dòng: BOUNDARY, INSIDE hoặc OUTSIDE.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.