CSES - Point in Polygon | Điểm trong đa giác
Xem PDF
Điểm:
2000
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một đa giác \(n\) đỉnh và một danh sách \(m\) điểm . Nhiệm vụ của bạn là xác định từng điểm là ở bên trong, bên ngoài hay trên cạnh của đa giác.
Đa giác gồm \(n\) đỉnh \((x_1,y_1),(x_2,y_2),...,(x_n,y_n)\). Hai đỉnh \((x_i,y_i)\) và \((x_{i+1},y_{i+1})\) là kề nhau với \(i=1,2,...,n−1,\) và hai đỉnh \((x_1,y_1)\) và \((x_n,y_n)\) cũng kề nhau.
Input
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) : số đỉnh của đa giác và số điểm.
- Tiếp theo là \(n\) dòng mô tả đa giác. Dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\).
- Giả sử đó là đa giác đơn, tức là nó không có cạnh giao nhau.
- Cuối cùng là \(m\) dòng mô tả các điểm. Mỗi dòng chứa hai số nguyên \(x\) và \(y\).
Output
- Với mỗi điểm, in ra
INSIDE,OUTSIDEhoặcBOUNDARY.
Constraints
- \(3 \le n \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\)
Example
Sample input
4 3
1 1
4 2
3 5
1 4
2 3
3 1
1 3
Sample output
INSIDE
OUTSIDE
BOUNDARY
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Downvote. Please remove it.
ok
spam hoài