Coloring

题意翻译

给定平面上的 $n$ 个点的坐标 $(x_i,y_i)$ ， **其中没有两点有相同的坐标** 。定义点 $i,j$ 间的距离为 $d(i,j)=|x_i-x_j|+|y_i-y_j|$ 。 现用 $n$ 种颜色对这些点进行染色，求满足以下条件的方案数： - 每种相同颜色的点两两间距离相等 - 每个点到具有不同颜色的点的距离总 **大于** 与其颜色相同的其他点（若存在）的距离。 答案取模 $998244353$ 。 $2\le n\le 100,0\le x_i,y_i\le 10^8$

题目描述

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.

输入输出格式

输入格式

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 $ ).

输出格式

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

输入输出样例

输入样例 #1

3
1 0
3 0
2 1

输出样例 #1

9

输入样例 #2

5
1 2
2 4
3 4
4 4
1 3

输出样例 #2

240

输入样例 #3

4
1 0
3 0
2 1
2 0

输出样例 #3

24

说明

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] $ .

**题目大意：**
在平面上有n个点，每个点的坐标为 $(x_i, y_i)$，并且没有两个点的坐标相同。两点i和j之间的距离定义为 $d(i,j) = |x_i - x_j| + |y_i - y_j|$。现在要用n种颜色对点进行染色，要求满足以下条件：
- 相同颜色的点两两之间的距离相等。
- 每个点到不同颜色的点的距离要大于与其颜色相同的其他点的距离（如果存在的话）。

需要计算满足这些条件的不同染色方式的数量，结果对 $998244353$ 取模。

**输入数据格式：**
第一行包含一个整数 $n$（$2 \le n \le 100$）——点的数量。

接下来n行，每行包含两个整数 $x_i$ 和 $y_i$（$0 \le x_i, y_i \le 10^8$）。

保证没有两个点的坐标相同。

**输出数据格式：**
输出一个整数——为点选择颜色的方式的数量，结果对 $998244353$ 取模。

**输入输出样例：**
**输入样例 #1：**
```
3
1 0
3 0
2 1
```
**输出样例 #1：**
```
9
```
**输入样例 #2：**
```
5
1 2
2 4
3 4
4 4
1 3
```
**输出样例 #2：**
```
240
```
**输入样例 #3：**
```
4
1 0
3 0
2 1
2 0
```
**输出样例 #3：**
```
24
```**题目大意：** 在平面上有n个点，每个点的坐标为 $(x_i, y_i)$，并且没有两个点的坐标相同。两点i和j之间的距离定义为 $d(i,j) = |x_i - x_j| + |y_i - y_j|$。现在要用n种颜色对点进行染色，要求满足以下条件： - 相同颜色的点两两之间的距离相等。 - 每个点到不同颜色的点的距离要大于与其颜色相同的其他点的距离（如果存在的话）。 需要计算满足这些条件的不同染色方式的数量，结果对 $998244353$ 取模。 **输入数据格式：** 第一行包含一个整数 $n$（$2 \le n \le 100$）——点的数量。 接下来n行，每行包含两个整数 $x_i$ 和 $y_i$（$0 \le x_i, y_i \le 10^8$）。 保证没有两个点的坐标相同。 **输出数据格式：** 输出一个整数——为点选择颜色的方式的数量，结果对 $998244353$ 取模。 **输入输出样例：** **输入样例 #1：** ``` 3 1 0 3 0 2 1 ``` **输出样例 #1：** ``` 9 ``` **输入样例 #2：** ``` 5 1 2 2 4 3 4 4 4 1 3 ``` **输出样例 #2：** ``` 240 ``` **输入样例 #3：** ``` 4 1 0 3 0 2 1 2 0 ``` **输出样例 #3：** ``` 24 ```