InPoly
Xem dạng PDF
Gửi bài giải
Điểm:
0,20 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Trên hệ tọa độ ~Oxy~, cho một đa giác lồi gồm ~n~ đỉnh. Có ~m~ truy vấn, mỗi truy vấn gồm một điểm, hãy kiểm tra xem điểm đó có nằm trong đa giác đã cho hay không.
Input
- Dòng đầu gồm số nguyên dương ~n~.
- ~n~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~ trên đa giác. Các đỉnh được nhập vào theo thứ tự ngược chiều kim đồng hồ.
- Dòng tiếp theo gồm số nguyên dương ~m~.
- ~m~ dòng sau, mỗi dòng gồm hai số ~x_i,y_i~ miêu tả tọa độ của điểm thuộc truy vấn ~i~.
Output
- Gồm ~m~ dòng, dòng ~i~ in ra ~0~ nếu điểm thứ ~i~ không nằm trong đa giác, ngược lại in ra ~1~.
Constraints
- ~1 \le n,m \le 10^3~.
- Tọa độ của các điểm đều là số nguyên trong khoảng ~[-10^6,10^6]~.
Sample Input 1
4
2 4
8 4
6 8
4 6
4
3 5
4 7
5 5
6 7
Sample Output 1
0
0
1
1
Bình luận
đề nghị tăng n, m <= 1e6 để hardcore hơn xíuuu
Nếu điểm nằm trên cạnh của đa giác thì in ra 0.
bài tương tự
https://oj.vnoi.info/problem/meterain
Bài tương tự