1003. 括号凸包

题目描述

给定二维平面上的 $n$ 个点，所有点互不相同，且不存在三点共线。每个点上写有一个括号，可能是左括号 $\texttt{(}$，也可能是右括号 $\texttt{)}$。

我们称一个字符串 $S$ 是一个合法括号序列，当且仅当它可以由如下递归规则生成：

• 空串是一个合法括号序列；
• 如果 $A$ 是合法括号序列，那么字符串 $\texttt{(}$ $A$ $\texttt{)}$ 也是合法括号序列；
• 如果 $A$ 和 $B$ 都是合法括号序列，那么 $AB$ 也是合法括号序列。

例如，$\texttt{()}$, $\texttt{(())}$, $\texttt{()()}$ 都是合法括号序列，而 $\texttt{)(}$, $\texttt{(()}$, $\texttt{())(}$ 不是合法括号序列。

现在，你需要从给定的点中选出若干个互不相同的点作为顶点，构成一个凸多边形。

在本题中，一个由 $m$ 个点 $p_{a_1},p_{a_2},\dots,p_{a_m}$ 构成的多边形被称为凸多边形，当且仅当满足：

• $m \ge 3$；
• 这些点按照 $a_1,a_2,\dots,a_m$ 的顺序依次连接，并连接 $a_m$ 与 $a_1$ 后，形成一个简单多边形（即多边形的边仅在相邻边的端点处相交，不相邻边互不相交）；
• 对于该多边形的每一条边，其余所有顶点都严格位于这条边所在直线的同一侧。

换句话说，所选出的点必须恰好按照它们在自身凸包上的环形顺序排列，并且所有内角都严格小于 $180^\circ$，凸多边形上不存在三点共线。

对于一个凸多边形，任选其边界上的一个顶点作为起点，并沿着多边形边界按顺时针或逆时针方向依次遍历所有顶点，最后回到起点前停止。这样可以得到一个长度为 $m$ 的括号序列：若当前顶点上写有左括号，则写下 $\texttt{(}$；若当前顶点上写有右括号，则写下 $\texttt{)}$。

你的任务是找到包含左括号的凸多边形，使得对于该多边形上的任意一个写有左括号的顶点，以它作为起点沿多边形边界并以任意方向遍历得到的括号序列都是合法括号序列。但这样的多边形数量很多，所以你决定只计算满足条件的多边形个数对 $998244353$ 取模后的结果。

输入格式

第一行包含一个整数 $T$（$1\le T\le 100$），表示数据组数。

每组数据的第一行包含一个整数 $n$（$1 \le n \le 500$），表示点的数量。

接下来 $n$ 行，每行包含三个整数 $x_i,y_i,t_i$（$0 \le x_i,y_i \le 10^9, t_i \in \{0,1\}$），表示第 $i$ 个点的坐标和括号类型，其中 $t_i = 0$ 表示左括号，$t_i = 1$ 表示右括号。

保证每组数据中所有点互不相同，且不存在三点共线。

保证所有数据的 $n$ 之和不超过 $1000$。

输出格式

对于每组数据，输出一行一个整数表示多边形的方案数取模后的结果

样例输入

5
4
1 1 0
2 4 1
3 9 0
4 16 1
5
1 1 0
2 4 0
3 9 0
4 16 1
5 25 1
6
47 58 0
30 23 0
27 34 1
35 7 1
10 30 1
1 25 1
8
10 5 0
10 16 0
1 5 0
24 9 0
6 2 0
6 12 0
7 18 1
3 13 1
1
0 0 0

样例输出

1
0
1
0
0

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1003