#P18589. Security at Museums

Security at Museums

Security at Museums

一座美术馆的平面形状是一个简单多边形,每个顶点处放置一件艺术品。

一群窃贼准备选择至少两件艺术品同时盗取,每件被选中的艺术品由一名窃贼负责。为了能彼此照应,他们要求任意两名窃贼都能看见对方:连接他们所在顶点的整条线段,都必须位于美术馆的内部或边界上。

作为美术馆管理员,你需要计算可能被选择的艺术品集合有多少种。两个集合只要所含顶点不同,就视为不同选择;窃贼的编号和分工不参与计数。

输出答案对 998244353998244353 取模的结果。

输入格式

第一行一个整数n,表示多边形的顶点数。

接下来n行,每行两个整数x、y,按逆时针顺序给出多边形各顶点的坐标。

输入只有一个多边形,不含测试用例数量T。

输出格式

输出一行一个整数,表示满足条件、大小至少为2的顶点集合数量对998244353取模的结果。

数据范围与保证

3≤n≤2003\le n\le200,−106≤x,y≤106-10^6\le x,y\le10^6。

所有顶点互不相同。多边形是简单多边形:除相邻两边在它们的公共顶点处接触外,任意两条边都不相交、也不相接触。

任意两条相邻的边不共线。不相邻的多个顶点仍可能共线。线段沿着多边形边界或经过其他顶点时,不能仅因此判为不可见,仍须检查整条线段是否处于闭多边形内。

样例输入 1

7
0 20
40 0
40 20
70 50
50 70
30 50
0 50

样例输出 1

56

样例输入 2

3
0 2022
-2022 -2022
2022 0

样例输出 2

4

样例说明

第二个样例是三角形。任意至少含两件艺术品的集合都满足条件,共有3个二元集合和1个三元集合。