Enclosed Points

题目描述

我们有一组位于二维平面上的 $N$ 个点构成的集合 $S$。第 $i$ 个点的坐标为 $(x_i, y_i)$。这 $N$ 个点具有不同的 $x$ 坐标且不同的 $y$ 坐标。 对于非空子集 $T$（$T \subseteq S$），令 $f(T)$ 为包含 $T$ 中所有点的、边与坐标轴平行的最小矩形中包含的点的个数。更正式地，我们如下定义 $f(T)$：

$f(T) :=$ （满足 $a \leq x_i \leq b$ 且 $c \leq y_i \leq d$ 的整数 $i$ 的个数（$1 \leq i \leq N$），其中 $a$、$b$、$c$、$d$ 分别是 $T$ 中点的最小 $x$ 坐标、最大 $x$ 坐标、最小 $y$ 坐标和最大 $y$ 坐标）

求在所有非空子集 $T$ 的情况下 $f(T)$ 的和。由于结果可能非常大，请对 $998244353$ 取模后输出。

输入格式

输入按下列格式由标准输入提供： $N$ $x_1$ $y_1$ : $x_N$ $y_N$

输出格式

输出在所有非空子集 $T$ 的情况下 $f(T)$ 的和，对 $998244353$ 取模。

3
-1 3
2 1
3 -2

13

4
1 4
2 1
3 3
4 2

34

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

7222

提示

$1 \leq N \leq 2 \times 10^5$ $-10^9 \leq x_i, y_i \leq 10^9$ $x_i \neq x_j (i \neq j)$ $y_i \neq y_j (i \neq j)$ 输入中的所有数值均为整数。令第一个、第二个和第三个点分别为 $P_1$、$P_2$ 和 $P_3$。$S = \{P_1, P_2, P_3\}$ 有七个非空子集，且 $f$ 在每个子集上的取值如下：

$f(\{P_1\}) = 1$ $f(\{P_2\}) = 1$ $f(\{P_3\}) = 1$ $f(\{P_1, P_2\}) = 2$ $f(\{P_2, P_3\}) = 2$ $f(\{P_3, P_1\}) = 3$ $f(\{P_1, P_2, P_3\}) = 3$

这些值的和为 $13$。
注意对 $998244353$ 取模后输出。

标签: AtCoder|abc136F

来源

AtCoder|abc136F