P11193 [COTS 2021] Bug Kukac

Translated from [Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2021/) D1T2. $\texttt{3s,0.5G}$。 As everyone knows, insects can only sense clockwise and counterclockwise directions. If you suspect the SPJ is incorrect, please contact the problem porter. [SPJ code](https://www.luogu.com.cn/paste/94gufjh7)。

**This is an interactive problem.** On a 2D plane, there is a polygon $P$ with $N$ points. Note that $P$ is **not necessarily** convex (it can be concave). We number the points on the polygon **in order** from $1$ to $N$. In addition, there is an extra point $0$. Determine through interaction whether it is inside $P$. **It is guaranteed that the polygon edges do not intersect. It is guaranteed that these $(N+1)$ points are pairwise distinct. It is guaranteed that no three points are collinear.** Definition: $A, B, C$ are in **counterclockwise order** if and only if, when looking from $A$ to $B$, point $C$ is on the left side of the line $AB$, as shown in the left figure.  【Implementation Details】 Before the interaction starts, you need to read a line with two integers $N, Q$, representing the number of vertices of the polygon and the maximum number of queries allowed. Then, your program interacts with the interactive library through standard input/output. The following queries are allowed: - $\texttt{? a b c}$: Ask whether points $a, b, c$ are in counterclockwise order. You must ensure that $a, b, c$ are pairwise distinct, and that $0 \le a, b, c \le N$. If $a, b, c$ are in counterclockwise order, the answer is $1$; otherwise, the answer is $0$. After you determine the answer, output it in the following format: - $\texttt{! x}$: If $x = 1$, it means point $0$ is inside the polygon; if $x = 0$, it means point $0$ is not inside the polygon. After each output, do not forget to flush the buffer, for example: `std::cout.flush()`。

See 【Implementation Details】.

See 【Implementation Details】.

#### Sample Explanation  #### Constraints For $100\%$ of the testdata, it is guaranteed that $3 \le N \le 500$. Reminder again: **the polygon is not necessarily convex**. It is guaranteed that the polygon edges do not intersect. It is guaranteed that these $(N+1)$ points are pairwise distinct. It is guaranteed that no three points are collinear. | Subtask ID | $N \le$ | $Q =$ | Special Property | Score | | :--: | :--: | :--: | :--: | :--: | | $1$ | $50$ | $N^3$ | Yes | $5$ | | $2$ | $50$ | $N^3$ | No | $25$ | | $3$ | $500$ | $N^2$ | No | $15$ | | $4$ | $500$ | $4N$ | No | $25$ | | $5$ | $500$ | $2N$ | No | $30$ | Special Property: $P$ is convex. Translated by ChatGPT 5