← 返回题目列表

AtCoder · utpc2020_m

M. 不是另一个几何游戏!

中文机器翻译题面 查看原题

問題文

冒险者 Platypus 小伙和 Qlatyqus 小伙正在攻略分布在巨大平原上的地下城。 2 人 N 他们进行了为期 日的冒险,1 每一天,Platypus 小伙或 Qlatyqus 小伙会攻略某个地点的地下城。 具体来说,i 日目 (1\leq i \leq N) 有 A_i 是 在 P 的时候是 Platypus 小伙,而 A_i 是 在 Q 的时候是 Qlatyqus 小伙,在坐标 (X_i, Y_i) 的地下城。在这里,X_i,Y_i 是整数。 为了攻略尽可能广范围的地下城,

为了尽可能攻略更广范围的地下城,2 从人们应该尽可能合作的角度来看,i 第几天时的 2 对人的奖励金 S_i 定义如下。

  • Platypus 小朋友在 i 第几天之前攻略的某个地下城的分数,以及 Qlatyqus 小朋友的 i 日目之前攻略的某个地下城的点,2 考虑取这些点中点的操作。通过此操作得到的所有中点的集合, M 。M 的点全都包含在内的凸多边形中,其面积最小的面积称为 S_i 。但是,如果存在可以任意小的凸多边形面积,S_i=0 。

Platypus 和 Qlatyqus 想要1 计算每天的奖励金是多少。他们的 N 地下城攻略信息在这些天内被提供,i 第几天时的 2 对人的奖励金 S_i 该值应乘以 1 请制作一个按天报告的程序。不过,所求的值可以被证明是有理数,正如注释中所述, \bmod 998244353 请输出。

出力方法
输出有理数时,需首先将该有理数用分数表示  \frac p q 。在这里,p, q 是一个整数并且q 是 您也可以写 998244353 不能被整除(在此问题的约束下,这种表示总是可能的)。然后, p\equiv qr\pmod{998244353}  输出有多少个 0 以上 998244353 输出小于该分数的唯一整数 r 请输出。

制約

  • 1 \leq N \leq 2 \times 10^5
  • X_i, Y_i 是一个整数,0 \leq X_i, Y_i \lt 998244353 \ (1 \leq i \leq N) 小于
  • A_i 是一个字符 P 或 Q 任何一个
  • i \neq j 和 A_i = A_j 如果 (X_i, Y_i) \neq (X_j, Y_j)

入力

输入是按以下格式从标准输入给出的。

N
A_1 X_1 Y_1
\vdots
A_N X_N Y_N

出力

N 行。i 行中, i 每天的奖励金值 S_i 按照输出方法进行输出。


入力例1

5
P 0 1
Q 1 0
P 2 1
Q 1 2
Q 2 2

出力例1

0
0
0
1
748683266
  • 1 第 N 天 Platypus 在坐标 (0,1) 的地城。由于 Qlatyqus 还没有攻略过任何地城,所以奖励金在 0 。
  • 2 日时,Qlatyqus 将攻略位于 (1,0) 的地城。通过初日攻略的地城与 2 日攻略的地城的中点,可以取包含 \left(\frac{1}{2},\frac{1}{2}\right) 但是, 不是1 点的任意小的凸多边形,因此奖励金仍然是 0 。
  • 出于同样的原因, 3 第一天的奖金是 0 。
  • 4 到第二天时,如下图所示,紫色表示的点表示中点的集合 M ,紫色多边形表示 M 所包含的凸多边形。
    4 到第几天为止的地下城攻略情况(蓝点表示 Platypus 君,红点表示 Qlatyqus 君攻略的地下城位置)

    因此奖金是 1 。 对于
  • 最终日中点的集合 M 与凸多边形如下图所示。
    最终的地下城攻略状况

    因此奖金是 \frac{5}{4} 如下。请注意输出方法。

入力例2

8
P 0 0
Q 0 0
P 0 998244352
Q 0 998244352
P 998244352 0
Q 998244352 0
P 998244352 998244352
Q 998244352 998244352

出力例2

0
0
0
0
623902721
499122177
124780545
1