← 返回题目
题库练习 [ABC136F] Enclosed Points
← 上一题 下一题 →

A7614 | [ABC136F] Enclosed Points

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

在二维平面上有 $N$ 个点组成的集合 $S$，第 $i$ 个点的坐标为 $(x_i, y_i)$。所有点的 $x$ 坐标和 $y$ 坐标各不相同。

对于 $S$ 的任意非空子集 $T$，定义 $f(T)$ 为：覆盖 $T$ 中所有点且各边与坐标轴平行的最小矩形，包含的 $S$ 中的点的个数。更准确地说：

- 设 $T$ 中点的 $x$ 坐标的最小值和最大值分别为 $a, b$，$y$ 坐标的最小值和最大值分别为 $c, d$，则 $f(T)$ 等于满足 $a \leq x_i \leq b$ 且 $c \leq y_i \leq d$ 的 $1 \leq i \leq N$ 的点的个数。

请计算 $S$ 的所有非空子集 $T$ 的 $f(T)$ 之和。答案可能很大，请输出对 $998244353$ 取模的结果。

输入格式

输入按以下格式从标准输入读入。

> $N$
> $x_1$ $y_1$
> $\vdots$
> $x_N$ $y_N$

输出格式

请输出 $S$ 的所有非空子集 $T$ 的 $f(T)$ 之和对 $998244353$ 取模的结果。

输入输出样例

输入 #1
3
-1 3
2 1
3 -2
输出 #1
13
输入 #2
4
1 4
2 1
3 3
4 2
输出 #2
34
输入 #3
10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6
输出 #3
7222
C++ 编辑器
输入
输出