#P18589. Security at Museums
Security at Museums
Security at Museums
一座美术馆的平面形状是一个简单多边形,每个顶点处放置一件艺术品。
一群窃贼准备选择至少两件艺术品同时盗取,每件被选中的艺术品由一名窃贼负责。为了能彼此照应,他们要求任意两名窃贼都能看见对方:连接他们所在顶点的整条线段,都必须位于美术馆的内部或边界上。
作为美术馆管理员,你需要计算可能被选择的艺术品集合有多少种。两个集合只要所含顶点不同,就视为不同选择;窃贼的编号和分工不参与计数。
输出答案对 取模的结果。
输入格式
第一行一个整数n,表示多边形的顶点数。
接下来n行,每行两个整数x、y,按逆时针顺序给出多边形各顶点的坐标。
输入只有一个多边形,不含测试用例数量T。
输出格式
输出一行一个整数,表示满足条件、大小至少为2的顶点集合数量对998244353取模的结果。
数据范围与保证
,。
所有顶点互不相同。多边形是简单多边形:除相邻两边在它们的公共顶点处接触外,任意两条边都不相交、也不相接触。
任意两条相邻的边不共线。不相邻的多个顶点仍可能共线。线段沿着多边形边界或经过其他顶点时,不能仅因此判为不可见,仍须检查整条线段是否处于闭多边形内。
样例输入 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个三元集合。