P3316 [SDOI2014] Inside or Outside

upd: - Testdata update: a total of 10 test points from the original problem are selected, and two that did not meet the statement have been removed.

Alice gives a simple $N$-gon on the plane. A simple $N$-gon consists of $N$ given endpoints and straight segments connecting adjacent points. In particular, we consider vertex $1$ adjacent to vertex $N$. For distinct boundary segments, they only intersect at common endpoints. Sometimes Alice points to a point in the plane and asks Bob: “Is this point inside the polygon, outside the polygon, or on the boundary?” At that time, if the pointed point is a vertex of the polygon or lies on any edge of the polygon, it is considered to be on the boundary. Sometimes, to increase the difficulty, Alice deletes the edge connecting $a$ and $b$, inserts a new point $c$ (the newly inserted point is guaranteed not to coincide with any existing endpoint and not to lie on any existing edge), and then adds edges from $a$ to $c$ and from $b$ to $c$, thereby obtaining a new simple polygon. Alice guarantees that the figure obtained by such an operation is always a simple polygon. What Bob has to do is answer Alice’s questions correctly. In fact, each of Alice’s questions will be determined by Bob’s previous answer: although this answer is unique, it implies that if Bob cannot answer the previous question, he cannot get Alice’s next question. However, Alice’s modifications are indeed prepared in advance. In detail: each modification command by Alice can be viewed as a 6-tuple $\langle x_a, y_a, x_b, y_b, x_c, y_c \rangle$, which means the edge between $(x_a, y_a)$ and $(x_b, y_b)$ is deleted, and a new point $(x_c, y_c)$ is inserted. We guarantee that the points at coordinates $(x_a, y_a)$ and $(x_b, y_b)$ always exist. Because Alice guarantees that all appearing points (this includes query points) have non-negative integer coordinates, all less than $10^9$, and among the polygon’s points (this does not include query points) any two points have distinct $x$-coordinates and also distinct $y$-coordinates. Therefore, for each query Alice will give 7 non-negative integers: $r$, $x_{\text{in}}$, $y_{\text{in}}$, $x_{\text{out}}$, $y_{\text{out}}$, $x_{\text{bd}}$, $y_{\text{bd}}$. The actual query point $(X, Y)$ for this query is determined by the previous query point $(x_0, y_0)$ and the previous answer. For example, if the previous query point was outside the polygon, then: $$ X = (r \times x_0 + x_{\text{out}}) \bmod 10^9 $$ $$ Y = (r \times y_0 + y_{\text{out}}) \bmod 10^9 $$ For the first query, assume $x_0 = y_0 = 0$, i.e., treat $(0, 0)$ as the previous query. Similarly, if the previous point was inside, replace $x_{\text{out}}, y_{\text{out}}$ with $x_{\text{in}}, y_{\text{in}}$; if it was on the boundary, use $x_{\text{bd}}, y_{\text{bd}}$.

The first line contains an integer $N$, the number of vertices of the initial polygon. Then follow $N$ lines, each with a pair of non-negative integers $x$ and $y$ ($0 \leq x, y < 10^9$). They describe all vertices of the polygon in some order and are indexed from $1$ to $N$. Here we only assume that the point $(10^{100}, 10^{100})$ in the plane is certainly outside the polygon. The next line contains an integer $Q$, the total number of operations. Each of the next $Q$ lines starts with a number $p$. If $p = 0$, it is a query; if $p = 1$, it is a modification. - For a query, the next 7 non-negative integers are: $r$, $x_{\text{in}}$, $y_{\text{in}}$, $x_{\text{out}}$, $y_{\text{out}}$, $x_{\text{bd}}$, $y_{\text{bd}}$. - For a modification, the next 6 integers are: $x_a$, $y_a$, $x_b$, $y_b$, $x_c$, $y_c$.

For each query operation, output a single line containing exactly one string: either `in`, `out`, or `bd` (all lowercase), indicating that the query point is inside the polygon, outside the polygon, or on the boundary, respectively.

For 100% of the testdata: $N \leq 50000$, $Q \leq 50000$, all coordinates are non-negative and less than $10^9$, and $r$ is either $1$ or $0$. Translated by ChatGPT 5