{"problem":{"name":"Polygon and Points","description":{"content":"There is a convex $N$\\-gon $S$ in the two-dimensional coordinate plane where the positive $x$\\-axis points to the right and the positive $y$\\-axis points upward. The vertices of $S$ have the coordinat","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc296_g"},"statements":[{"statement_type":"Markdown","content":"There is a convex $N$\\-gon $S$ in the two-dimensional coordinate plane where the positive $x$\\-axis points to the right and the positive $y$\\-axis points upward. The vertices of $S$ have the coordinates $(X_1,Y_1),\\ldots,(X_N,Y_N)$ in counter-clockwise order.\nFor each of $Q$ points $(A_i,B_i)$, answer the following question: is that point inside or outside or on the boundary of $S$?\n\n## Constraints\n\n*   $3 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq Q \\leq 2\\times 10^5$\n*   $-10^9 \\leq X_i,Y_i,A_i,B_i \\leq 10^9$\n*   $S$ is a strictly convex $N$\\-gon. That is, its interior angles are all less than $180$ degrees.\n*   $(X_1,Y_1),\\ldots,(X_N,Y_N)$ are the vertices of $S$ in counter-clockwise order.\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$X_1$ $Y_1$\n$\\vdots$\n$X_N$ $Y_N$\n$Q$\n$A_1$ $B_1$\n$\\vdots$\n$A_Q$ $B_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc296_g","tags":[],"sample_group":[["4\n0 4\n-2 2\n-1 0\n3 1\n3\n-1 3\n0 2\n2 0","ON\nIN\nOUT\n\nThe figure below shows $S$ and the given three points. The first point is on the boundary of $S$, the second is inside $S$, and the third is outside $S$.\n![image](https://img.atcoder.jp/abc296/828da6ca52e6b48a908ad06fa59eb9cb.png)"],["3\n0 0\n1 0\n0 1\n3\n0 0\n1 0\n0 1","ON\nON\nON"]],"created_at":"2026-03-03 11:01:14"}}