← 返回题目列表

Codeforces · 1697/E

E. 着色

中文机器翻译题面 查看原题

给定平面上 $$$n$$$ 个点,第 $$$i$$$ 个点的坐标为 $$$(x_i, y_i)$$$。没有两个点具有相同的坐标。

点 $$$i$$$ 和 $$$j$$$ 之间的距离定义为 $$$d(i,j) = |x_i - x_j| + |y_i - y_j|$$$。

对于每个点,您必须选择一种颜色,用 $$$1$$$ 到 $$$n$$$ 之间的整数表示。对于不同点 $$$(a,b,c)$$$ 的每个有序三元组,应满足以下约束:

- 如果 $$$a$$$、$$$b$$$ 和 $$$c$$$ 具有相同的颜色,则 $$$d(a,b) = d(a,c) = d(b,c)$$$;
- 如果 $$$a$$$ 和 $$$b$$$ 具有相同的颜色,并且 $$$c$$$ 的颜色与 $$$a$$$ 的颜色不同,则 $$$d(a,b) < d(a,c)$$$ 且 $$$d(a,b) < d(b,c)$$$。

计算选择满足这些约束的颜色的不同方法的数量。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 点数。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^8$$$)。

没有两个点具有相同的坐标(即,如果 $$$i \ne j$$$,则 $$$x_i \ne x_j$$$ 或 $$$y_i \ne y_j$$$)。

输出

打印一个整数 — 选择点颜色的方法数。由于它可能很大,因此打印它对 $$$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

注意

在第一次测试中,以下选择颜色的方式是合适的:

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