P11193 [COTS 2021] 虫 Kukac

译自 [Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2021/) D1T2。$\texttt{3s,0.5G}$。 众所周知，昆虫只对顺逆时针方向有感觉。 如果怀疑 SPJ 有误，请联系搬题人。[SPJ 代码](https://www.luogu.com.cn/paste/94gufjh7)。

**这是一道交互题。** 二维平面上有一个 $N$ 个点的多边形 $P$。注意 $P$ **不一定**是凸的（它可以是凹包）。我们将多边形上的点**依次**编号为 $1\sim N$。 此外，还有一个额外的点 $0$。试通过交互来确定它是否在 $P$ 内部。 **保证多边形的线段不交。保证这 $(N+1)$ 个点两两不同。保证无三点共线。** 定义：$A,B,C$ **逆时针排列**当且仅当从 $A$ 看向 $B$ 时，$C$ 在直线 $AB$ 左侧。如左图。  【实现细节】 交互开始前，需要读入一行两个整数 $N,Q$，表示多边形点数，和允许的最大询问数。 接下来，你的程序通过标准输入输出流与交互库交互。以下是允许的询问： - $\texttt{? a b c}$：询问点 $a,b,c$ 是否逆时针排列。必须保证 $a,b,c$ 两两不同，且 $0\le a,b,c\le N$。 如果 $a,b,c$ 逆时针排列，回答为 $1$；否则回答为 $0$。 确定答案后，按照以下格式回答： - $\texttt{! x}$：如果 $x=1$，则代表 $0$ 号点在多边形内部；$x=0$ 代表 $0$ 号点不在多边形内部。 每次输出后，别忘了刷新缓冲区。如：`std::cout.flush()`。

见【实现细节】。

见【实现细节】。

#### 样例解释  #### 数据范围 对于 $100\%$ 的数据，保证 $3\le N\le 500$。 再次提醒，**多边形不一定是凸的**。保证多边形的线段不交。保证这 $(N+1)$ 个点两两不同。保证无三点共线。 | 子任务编号 | $N\le $ | $Q=$ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | :--: | | $ 1 $ | $ 50 $ | $ N^3 $ | 有 | $ 5 $ | | $ 2 $ | $ 50 $ | $ N^3 $ | 无 | $ 25 $ | | $ 3 $ | $ 500 $ | $ N^2 $ | 无 | $ 15 $ | | $ 4 $ | $ 500 $ | $ 4N $ | 无 | $ 25 $ | | $ 5 $ | $ 500 $ | $ 2N $ | 无 | $ 30 $ | 特殊性质：$P$ 是凸的。