P6679 [COCI 2019/2020 #2] Zvijezda

Mirko 和 Slavko 正在通过玩多边形和观看新一季的《The Biggest Loser》来打发空闲时间。Mirko 最近画了一个有偶数个顶点 $N$ 的凸多边形。然后 Slavko 考虑每对相对的边（如果两边之间有 $\frac N2 - 1$ 条边，则它们是相对的），画出位于这些边上的直线，并将它们与包含多边形的平面部分一起着色。最后，Mirko 找到了一组 $Q$ 个点，并决定挑战 Slavko，要求他回答每个点是位于着色部分还是未着色部分。新的《The Biggest Loser》剧集即将开始，Slavko 没有时间回答 Mirko 的查询。你能帮助他吗？

第一行，一个整数 $T$，它用于生成 Mirko 查询的参数。该数字只能是 $0$ 或 $1$。 第二行，一个正整数 $n$。 第 $3 \sim n + 2$ 行，每行 $2$ 个正整数 $x_i, y_i$。表示多边形的一个顶点。顶点是按逆时针顺序给出的，没有三个连续的顶点是共线的。 第 $n + 3$ 行，一个正整数 $q$。 接下来 $q$ 行，每行都有两个整数 $a_i, b_i$，它们用作在第 $i$ 个 Mirko 查询中生成点的参数。$x_i$ 等于 Mirko 查询的第 $i$ 个（含 $i$ 点）在平面彩色部分上的点数。当然，$x_0 = 0$。然后，应将 Mirko 第 $i$ 个查询的点生成为： $$p_i = (a_i \oplus (T \times x^{3}_{i-1}), b_i \oplus(T \times x^{3}_{i-1}))$$ 其中 $\oplus$ 代表按位异或运算。

如果 Mirko 查询的第 $i$ 个点位于平面的有色部分，则输出的第 $i$ 行为 $\tt DA$。否则，第 $i$ 行为 $\tt NE$。

#### 数据规模及约定 本题采用捆绑测试。 | Subtask 编号 | 分值 | 数据范围 | | :-----------: | :-----------: | :-----------: | | $1$ | $20$ | $1 \le n, q \le 2000$，$T = 0$| | $2$ | $30$ | $1 \le n, q \le 10^5$，$T = 0$| | $3$ | $60$ | $1 \le n, q \le 10^5$，$T = 1$|。 此外，对于 $100\%$ 的数据，$0 \le |x_i|, |y_i| \le 10^9, 0 \le |a_i|, |b_i| \le 2 \times 10^{18}$。 #### 说明 **本题分值按 COCI 原题设置，满分 $110$。** **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #2](https://hsin.hr/coci/archive/2019_2020/contest2_tasks.pdf) *T5 Zvijezda*。** 题面翻译由 ChatGPT-4o 提供。