Coloring
Contest: Educational Codeforces Round 130 (Rated for Div. 2)
Difficulty rating: 2400
Tags: brute force, combinatorics, constructive algorithms, dp, geometry, graphs, greedy, implementation, math

You are given $$$n$$$ points on the plane, the coordinates of the $$$i$$$-th point are $$$(x_i, y_i)$$$. No two points have the same coordinates.

The distance between points $$$i$$$ and $$$j$$$ is defined as $$$d(i,j) = |x_i - x_j| + |y_i - y_j|$$$.

For each point, you have to choose a color, represented by an integer from $$$1$$$ to $$$n$$$. For every ordered triple of different points $$$(a,b,c)$$$, the following constraints should be met:

- if $$$a$$$, $$$b$$$ and $$$c$$$ have the same color, then $$$d(a,b) = d(a,c) = d(b,c)$$$;
- if $$$a$$$ and $$$b$$$ have the same color, and the color of $$$c$$$ is different from the color of $$$a$$$, then $$$d(a,b) < d(a,c)$$$ and $$$d(a,b) < d(b,c)$$$.

Calculate the number of different ways to choose the colors that meet these constraints.

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of points.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^8$$$).

No two points have the same coordinates (i. e. if $$$i \ne j$$$, then either $$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$).

Output format:
Print one integer — the number of ways to choose the colors for the points. Since it can be large, print it modulo $$$998244353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first test, the following ways to choose the colors are suitable:

- $$$[1, 1, 1]$$$;
- $$$[2, 2, 2]$$$;
- $$$[3, 3, 3]$$$;
- $$$[1, 2, 3]$$$;
- $$$[1, 3, 2]$$$;
- $$$[2, 1, 3]$$$;
- $$$[2, 3, 1]$$$;
- $$$[3, 1, 2]$$$;
- $$$[3, 2, 1]$$$.

Example input:
3
1 0
3 0
2 1

Example output:
9

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

Example output:
240

Editorial:
Let's call a point $$$i$$$ isolated if its color does not match the color of any other point. If a point is not isolated, then it has the same color as the points with minimum distance to it (and only these points should have this color).
Let's build a directed graph where the arc $$$i \rightarrow j$$$ means that the point $$$j$$$ is one of the closest to the point $$$i$$$ (i. e. $$$d(i, j) = \min\limits_{k = 1, k \ne i}^{n} d(i,k)$$$). If there is a path from the vertex $$$i$$$ to the vertex $$$j$$$, it means that if the vertex $$$i$$$ is not isolated, the vertex $$$j$$$ should have the same color as vertex $$$i$$$.
Suppose the set of vertices reachable from $$$i$$$ (including $$$i$$$ itself) is $$$S(i)$$$. Finding $$$S(i)$$$ is easy — just run DFS from the vertex $$$i$$$. Let's analyze two cases:
• there exists a pair of vertices $$$(j, k)$$$ such that $$$j \in S(i)$$$, $$$k \in S(i)$$$, and there is no arc from $$$j$$$ to $$$k$$$;
• for every pair of vertices $$$(j, k)$$$ such that $$$j \in S(i)$$$ and $$$k \in S(i)$$$, there is an arc $$$j \rightarrow k$$$.
Why do we need to analyze these two cases? In the first case, the vertex $$$i$$$ must be isolated, because painting it and some other vertex into the same color means that every vertex from $$$S(i)$$$ will have this color, and it will break the condition in the statement. In the second case, the vertex $$$i$$$ may be isolated, or it may have the same color as all vertices in $$$S(i)$$$ — and if it is isolated, then the whole set $$$S(i)$$$ should consist of isolated vertices.
Let's find all such set of vertices that meet the second case. Each vertex will belong to at most one of these sets; if it doesn't belong to any, it must be isolated, otherwise either the whole its set consists of isolated vertices, or the whole set has the same color. So, for each set, we either use $$$1$$$ color or $$$|S(i)|$$$ colors. This allows us to implement a knapsack-like dynamic programming: let $$$dp_{i,j}$$$ be the number of ways to paint $$$i$$$ first sets into $$$j$$$ colors, such that the colors are not ordered. After running this dynamic programming, we can get the answer by simple combinatorics: iterate on the number of colors we use in these sets in total, multiply the dynamic programming for it by the (ordered) number of ways to choose these colors from $$$n$$$, and then by the number of ways to choose the colors for points that must be isolated.
This dynamic programming can even be implemented a bit easier if we treat every vertex that must be isolated as a set of size $$$1$$$, and this is the way it's written in the model solution.