CSES 2192 - Point in Polygon

給你一個有 \(n\) 個頂點的多邊形與一串 \(m\) 個點。你的任務是對每個點判斷它在多邊形的內部、外部，還是在多邊形的邊界上。

這個多邊形由 \(n\) 個頂點 \((x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\) 組成。對 \(i=1,2,\dots,n-1\)，頂點 \((x_i,y_i)\) 與 \((x_{i+1},y_{i+1})\) 相鄰，而頂點 \((x_1,y_1)\) 與 \((x_n,y_n)\) 也相鄰。

輸入格式

第一行輸入有兩個整數 \(n\) 與 \(m\)：多邊形的頂點數量與點的數量。

接下來有 \(n\) 行描述這個多邊形，第 \(i\) 行有兩個整數 \(x_i\) 與 \(y_i\)。

你可以假設這個多邊形是簡單多邊形，也就是它不會自我相交。

最後有 \(m\) 行描述這些點，每行有兩個整數 \(x\) 與 \(y\)。

輸出格式

對每個點，輸出 INSIDE、OUTSIDE 或 BOUNDARY。

範例輸入 1

4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3

範例輸出 1

INSIDE
OUTSIDE
BOUNDARY

限制

• \(3 \le n,m \le 1000\)
• \(1 \le m \le 1000\)
• \(-10^9 \le x_i, y_i \le 10^9\)
• \(-10^9 \le x, y \le 10^9\)

題目來源

CSES - Point in Polygon

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。