AT_utpc2020_m.Not Another Geometry Game!

冒险者 Platypus 君和 Qlatyqus 君正在探索一片广阔的平原，他们一天一个地点，轮流挑战多个分散的地牢。总共的冒险天数为 $N$ 天。在第 $i$ 天 $(1 \leq i \leq N)$，如果 $A_i$ 为 P，则表示当天由 Platypus 君前往坐标 $(X_i, Y_i)$ 的地牢挑战；如果 $A_i$ 为 Q，则当天由 Qlatyqus 君前往同样坐标的地牢挑战，$X_i, Y_i$ 为整数。

为了鼓励两人协作，他们每天获得的奖金 $S_i$ 由以下标准定义：

• 考虑 Platypus 君和 Qlatyqus 君在第 $i$ 天之前攻略的所有地牢坐标，并计算出所有可能的中点集合 $M$。$S_i$ 是能包含所有中点的最小凸多边形面积。如果这种凸多边形的面积可以任意接近零，那么 $S_i = 0$。

他们希望每天能知道他们的奖金多少。根据 $N$ 天内的地牢攻略数据，请编写一个程序，计算并输出他们每日的奖金 $S_i$。由于结果可能是有理数，需要对 $998244353$ 取模输出。

输出方法：将有理数表示为分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q$ 不可被 $998244353$ 整除（在本题限制条件下，总能找到这样的表示）。求出满足 $p \equiv qr \pmod{998244353}$ 的唯一整数 $r$（$0 \leq r < 998244353$）并输出 $r$。

标准输入如下：

• 第一行输入一个整数 $N$
• 接下来的 $N$ 行，每行输入三个值 $A_i$（字符 P 或 Q），$X_i$ 和 $Y_i$（两个整数）

输出 $N$ 行，第 $i$ 行表示第 $i$ 天他们的奖金 $S_i$，按之前描述的方法输出结果。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq X_i, Y_i < 998244353$
• 如果 $A_i = A_j$ 且 $i \neq j$，则 $(X_i, Y_i) \neq (X_j, Y_j)$

示例解释

• 第 1 天只有 Platypus 君一个人在坐标 $(0,1)$ 攻略地牢，没有 Qlatyqus 君的地牢记录，奖金为 0。
• 第 2 天，Qlatyqus 君在坐标 $(1,0)$ 攻略地牢，虽然有了中点 $\left(\frac{1}{2},\frac{1}{2}\right)$，但只有一个中点点，不足以形成有限面积的凸多边形，因此奖金依旧为 0。
• 第 3 天经过类似操作，奖金依旧为 0。
• 第 4 天，构成了如图所示的中点集合 $M$，使得形成一个面积为 1 的凸多边形，所以奖金为 1。
• 最终的中点集合 $M$ 以及相应的凸多边形如图所示，奖金为 $\frac{5}{4}$。根据输出要求进行取模计算。

本翻译由 AI 自动生成