CF1326G.Spiderweb Trees

Let's call a graph with $n$ vertices, each of which has it's own point $A_i = (x_i, y_i)$ with integer coordinates, a planar tree if:

• All points $A_1, A_2, \ldots, A_n$ are different and no three points lie on the same line.
• The graph is a tree, i.e. there are exactly $n-1$ edges there exists a path between any pair of vertices.
• For all pairs of edges $(s_1, f_1)$ and $(s_2, f_2)$, such that $s_1 \neq s_2, s_1 \neq f_2,$ $f_1 \neq s_2$, and $f_1 \neq f_2$, the segments $A_{s_1} A_{f_1}$ and $A_{s_2} A_{f_2}$ don't intersect.

Imagine a planar tree with $n$ vertices. Consider the convex hull of points $A_1, A_2, \ldots, A_n$. Let's call this tree a spiderweb tree if for all $1 \leq i \leq n$ the following statements are true:

• All leaves (vertices with degree $\leq 1$) of the tree lie on the border of the convex hull.
• All vertices on the border of the convex hull are leaves.

An example of a spiderweb tree:

The points $A_3, A_6, A_7, A_4$ lie on the convex hull and the leaf vertices of the tree are $3, 6, 7, 4$.

Refer to the notes for more examples.

Let's call the subset $S \subset {1, 2, \ldots, n}$ of vertices a subtree of the tree if for all pairs of vertices in $S$, there exists a path that contains only vertices from $S$. Note that any subtree of the planar tree is a planar tree.

You are given a planar tree with $n$ vertexes. Let's call a partition of the set ${1, 2, \ldots, n}$ into non-empty subsets $A_1, A_2, \ldots, A_k$ (i.e. $A_i \cap A_j = \emptyset$ for all $1 \leq i \lt j \leq k$ and $A_1 \cup A_2 \cup \ldots \cup A_k = {1, 2, \ldots, n}$) good if for all $1 \leq i \leq k$, the subtree $A_i$ is a spiderweb tree. Two partitions are different if there exists some set that lies in one parition, but not the other.

Find the number of good partitions. Since this number can be very large, find it modulo $998\,244\,353$.

我们称一个具有 $n$ 个顶点的图（每个顶点 $A_i = (x_i, y_i)$ 具有整数坐标）为平面树，若满足以下条件：

• 所有点 $A_1, A_2, \ldots, A_n$ 互不相同，且任意三点不共线；
• 该图是一棵树，即恰好有 $n-1$ 条边，且任意两个顶点之间均存在一条路径；
• 对于任意两条边 $(s_1, f_1)$ 和 $(s_2, f_2)$，若满足 $s_1 \neq s_2$、$s_1 \neq f_2$、$f_1 \neq s_2$ 且 $f_1 \neq f_2$，则线段 $A_{s_1} A_{f_1}$ 与 $A_{s_2} A_{f_2}$ 不相交。

考虑一个含 $n$ 个顶点的平面树。设 $A_1, A_2, \ldots, A_n$ 的凸包为该点集的凸包。若对所有 $1 \leq i \leq n$，以下两个条件均成立，则称该树为蛛网树（spiderweb tree）：

• 树的所有叶子（度数 $\leq 1$ 的顶点）均位于凸包的边界上；
• 凸包边界上的所有顶点均为叶子。

一个蛛网树示例：

其中点 $A_3, A_6, A_7, A_4$ 位于凸包上，而该树的叶子顶点为 $3, 6, 7, 4$。

更多示例请参见题目附注。

我们称顶点集合 $S \subset \{1, 2, \ldots, n\}$ 为该树的一个子树，当且仅当对 $S$ 中任意两个顶点，均存在一条仅由 $S$ 中顶点构成的路径。注意：平面树的任意子树本身也是平面树。

现给定一个含 $n$ 个顶点的平面树。将集合 $\{1, 2, \ldots, n\}$ 划分为若干非空子集 $A_1, A_2, \ldots, A_k$（即对所有 $1 \leq i < j \leq k$，有 $A_i \cap A_j = \emptyset$，且 $A_1 \cup A_2 \cup \ldots \cup A_k = \{1, 2, \ldots, n\}$），若对每个 $1 \leq i \leq k$，子树 $A_i$ 均为蛛网树，则称该划分为好划分（good partition）。若存在某个子集属于一个划分但不属于另一个划分，则称这两个划分不同。

求好划分的总数。由于该数可能极大，请输出其对 $998\,244\,353$ 取模的结果。

The first line contains an integer $n$ ($1 \leq n \leq 100$) — the number of vertices in the tree.

The next $n$ lines each contain two integers $x_i, y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$) — the coordinates of $i$-th vertex, $A_i$.

The next $n-1$ lines contain two integers $s, f$ ($1 \leq s, f \leq n$) — the edges $(s, f)$ of the tree.

It is guaranteed that all given points are different and that no three of them lie at the same line. Additionally, it is guaranteed that the given edges and coordinates of the points describe a planar tree.

第一行包含一个整数 $n$（$1 \leq n \leq 100$）——树中顶点的数量。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$（$-10^9 \leq x_i, y_i \leq 10^9$）——第 $i$ 个顶点 $A_i$ 的坐标。

接下来的 $n-1$ 行，每行包含两个整数 $s, f$（$1 \leq s, f \leq n$）——树的边 $(s, f)$。

保证所有给定的点互不相同，且其中任意三点不共线。此外，保证所给的边和点的坐标描述了一棵平面树。

Print one integer — the number of good partitions of vertices of the given planar tree, modulo $998\,244\,353$.

输出一个整数——给定平面树的顶点的“好划分”数量，对 $998\,244\,353$ 取模。

The picture for the first sample.

In the first test case, all good partitions are:

1. ${1}$, ${2}$, ${3}$, ${4}$;
2. ${1, 2}$, ${3}$, ${4}$;
3. ${1, 3}$, ${2}$, ${4}$;
4. ${1, 4}$, ${2}$, ${3}$;
5. ${1, 2, 3, 4}$.

The partition ${1, 2, 3}$, ${4}$ isn't good, because the subtree ${1, 2, 3}$ isn't spiderweb tree, since the non-leaf vertex $1$ lies on the convex hull.

The partition ${2, 3, 4}$, ${1}$ isn't good, because the subset ${2, 3, 4}$ isn't a subtree.

The picture for the second sample.

In the second test case, the given tree isn't a spiderweb tree, because the leaf vertex $1$ doesn't lie on the convex hull. However, the subtree ${2, 3, 4, 5}$ is a spiderweb tree.

The picture for the third sample.

The picture for the fourth sample.

In the fourth test case, the partition ${1, 2, 3, 4}$, ${5, 6, 7, 8}$ is good because all subsets are spiderweb subtrees.

第一个样例的示意图。

在第一个测试用例中，所有合法的划分如下：

1. ${1}$, ${2}$, ${3}$, ${4}$；
2. ${1, 2}$, ${3}$, ${4}$；
3. ${1, 3}$, ${2}$, ${4}$；
4. ${1, 4}$, ${2}$, ${3}$；
5. ${1, 2, 3, 4}$。

划分 ${1, 2, 3}$, ${4}$ 不合法，因为子树 ${1, 2, 3}$ 不是蛛网树（spiderweb tree），原因是其非叶节点 $1$ 位于凸包上。

划分 ${2, 3, 4}$, ${1}$ 不合法，因为子集 ${2, 3, 4}$ 并非一棵子树。

第二个样例的示意图。

在第二个测试用例中，给定的树本身不是蛛网树，因为叶节点 $1$ 不在凸包上。然而，子树 ${2, 3, 4, 5}$ 是蛛网树。

第三个样例的示意图。

第四个样例的示意图。

在第四个测试用例中，划分 ${1, 2, 3, 4}$, ${5, 6, 7, 8}$ 是合法的，因为其中每个子集均为蛛网子树。