#P17916. Many Convex Polygons

Many Convex Polygons

题目描述

给定一个凸多边形的 nn 个顶点,按逆时针顺序依次为 P0,P1,…,Pn−1P_0,P_1,\ldots,P_{n-1}。任意三个顶点都不共线。

对于每个 k=3,4,…,nk=3,4,\ldots,n,从这些顶点中任选 kk 个,按它们在原多边形边界上的顺序连接,得到一个凸 kk 边形。不同的顶点子集视为不同选法。

请对每个 kk,计算所有这类凸 kk 边形的面积之和的两倍,并对 998244353998244353 取模。

输入格式

每个文件只有一组数据。

第一行是整数 nn。接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示对应顶点的坐标。输入顺序为逆时针顺序。

输出格式

输出 n−2n-2 行。第 ii 行给出 k=i+2k=i+2 时的答案模 998244353998244353 的结果。面积和的两倍一定是整数。

数据范围

3≤n≤2×1053\le n\le2\times10^5,−109≤xi,yi≤109-10^9\le x_i,y_i\le10^9。

保证给出的点按顺序构成凸多边形,且任意三个点不共线。

样例

6
0 0
1 0
2 1
2 2
1 2
0 1
36
54
30
6