Spiderweb Trees
Contest: Codeforces Global Round 7
Difficulty rating: 3500
Tags: dp, geometry, 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 < 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$$$.

Input format:
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.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4
0 0
0 1
-1 -1
1 -1
1 2
1 3
1 4

Example output:
5

Example input:
5
3 2
0 -3
-5 -3
5 -5
4 5
4 2
4 1
5 2
2 3

Example output:
8

Editorial:
Let's hang the tree on the vertex $$$1$$$. After that, we will calculate the value $$$dp_i$$$ for all vertices $$$i$$$, which is equal to the number of good partitions of the subtree of the vertex $$$i$$$ (subtree in the rooted tree). The answer to the problem in these definitions is $$$dp_1$$$.
To calculate these values let's make dfs. We know in the vertex $$$p$$$ and we want to calculate $$$dp_p$$$. We know the values $$$dp_i$$$ for all $$$i$$$ in the subtree of $$$p$$$. Let's define the set of the partition, which contains $$$p$$$ as $$$S$$$.
There are some cases:
Case $$$1$$$: $$$|S| = 1$$$. In this case, the number of good partitions is $$$dp_{i_1} dp_{i_2} \ldots dp_{i_k}$$$, there $$$i_1, i_2, \ldots, i_k$$$ are all sons of the vertex $$$p$$$.
Case $$$2$$$: $$$|S| = 2$$$. In this case, the number of good partitions is $$$\sum\limits_{i \in Sons(p)} {f_i \prod\limits_{j \in Sons(p), j \neq i} dp_{j}}$$$, there $$$f_i = dp_{i_1} dp_{i_2} \ldots dp_{i_k}$$$, there $$$i_1, i_2, \ldots, i_k$$$ are all sons of the vertex $$$i$$$.
The values in these cases are easy to find. We have one, last case:
Case $$$3$$$: $$$|S| \geq 3$$$.
In this case, the number of good partitions is $$$\sum\limits_{p \in S, \, S \, is \, spiderweb} func(S)$$$. Let's define $$$func(S)$$$ as the product of $$$dp_i$$$ for all vertices $$$i$$$, which are going from $$$S$$$ (it means, that $$$i$$$ isn't in $$$S$$$, but ancestor of $$$i$$$ is in $$$S$$$). Let's try to calculate this sum faster.
Let's call a pair of vertices $$$(i, j)$$$ good if they are not connected and all vertices $$$t$$$ on the path from $$$i$$$ to $$$j$$$ lies on the left side from the vector $$$\overrightarrow{A_i A_j}$$$. It can be shown, that if the polygon $$$A_{i_1} A_{i_2} \ldots A_{i_k}$$$ is convex and all pairs $$$(i_{j}, i_{j+1})$$$ are good, the subtree with leafs $$$i_1, i_2, \ldots, i_k$$$ is spiderweb.
So, let's fix all leaf vertices in $$$S$$$: $$$i_1, i_2, \ldots, i_k$$$ (these are the vertices of the subtree of $$$p$$$, they can be equal to $$$p$$$). If $$$S$$$ is the spiderweb tree, the ways $$$(i_j, i_{j+1})$$$ divide the plane into infinite parts (for explanation look at the picture):
The part is defined only with the way in the tree. Let's define $$$value_{ij}$$$ as the product of $$$dp_t$$$ for all vertices $$$t$$$, such that $$$A_t$$$ lies in the part for the way $$$(i, j)$$$, the vertex $$$t$$$ doesn't lie on the way and the ancestor of $$$t$$$ lies on the way. So, it's easy to see, that $$$func(S) = \prod\limits_{i=1}^{k} {value_{i_j i_{j+1}}}$$$. We can calculate the value for each path only one time during the dfs, after the moment, when all needed values of dp will be defined.
So, let's take all pairs of vertices $$$(i, j)$$$, such that $$$i$$$ and $$$j$$$ are in the subtree of vertex $$$p$$$, the way $$$(i, j)$$$ is good and the point $$$A_p$$$ lies on the left side from the vector $$$\overrightarrow{A_i A_j}$$$. After that, we should calculate the sum of products of $$$value_{i_j i_{j+1}}$$$ for all convex polygons $$$A_{i_1} A_{i_2} \ldots A_{i_k}$$$, which contains the vertex $$$p$$$ on some path $$$(i_j i_{j+1)}$$$. This thing can be done by the standard dp in time $$$O(n^3)$$$ (the same dp as how we calculate the number of convex polygons). To fix the last condition we can make this dp two times: with all good pairs and with good pairs, which don't contain the vertex $$$p$$$. After that, the needed number is the subtraction of these two numbers.
So, we have the solution with time complexity $$$O(n^4)$$$.