Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 難易度: [表示] ハック可能 ✓
統計

凸多角形の $n$ 個の頂点 $P(0), P(1), \cdots, P(n - 1)$ が反時計回りの順に与えられます。この中から $k$ 個の頂点 $P(i_0), P(i_1), \cdots, P(i_{k-1})$ ($0 \le i_0 < i_1 < \cdots < i_{k-1} < n$) を選ぶ方法は $\binom{n}{k}$ 通りあります。選ばれた頂点を反時計回りの順に結ぶ(すなわち、各 $0 \le j < k$ について頂点 $P(i_j)$ と $P(i_{(j+1) \bmod k})$ を結ぶ)ことで、$k$ 個の頂点からなる凸多角形を作ることができます。

各 $3 \le k \le n$ について、上記の方法で作られる $k$ 個の頂点を持つすべての凸多角形を考えます。これらの凸多角形の面積の総和の $2$ 倍を求めてください。

入力

各テストファイルには $1$ つのテストケースのみが含まれます。

$1$ 行目には、凸多角形の頂点数を表す整数 $n$ ($3 \le n \le 2 \times 10^5$) が与えられます。

続く $n$ 行のうち $i$ 行目には、凸多角形の $i$ 番目の頂点の座標を表す $2$ つの整数 $x_i$ と $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) が与えられます。頂点は反時計回りの順に与えられ、どの $3$ 頂点も同一直線上にはありません。

出力

$(n - 2)$ 行出力してください。各行には $1$ つの整数を出力し、$i$ 行目には $k = i + 2$ に対する答えを出力してください。

答えは整数になることが証明できます。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入出力例

入力例 1

6
0 0
1 0
2 1
2 2
1 2
0 1

出力例 1

36
54
30
6

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.