问题 AZ: 你的名字
内存限制:1024 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:44
解决:16
题目描述
本题讨论范围是二维坐标平面。
集合S SS有N NN个点,第i ii个点的坐标是( x i , y i ) (x_i, y_i)(xi,yi)
其中这N NN个点的横纵坐标各不相同。
对于S SS的一个非空子集T TT,定义f ( T ) f(T)f(T)为:最小的 能框住T TT中所有点的最小水平矩形框 所框住的点的个数。
通俗地说:
给定一个集合T TT,我们可以唯一确定一个矩形,满足:
- 矩形的边平行于x xx轴和y yy轴
- 矩形能覆盖所有的集合T TT中的点
- 矩形是满足条件的所有矩形
那么这个矩形所能覆盖的S SS中的点的个数即为f ( T ) f(T)f(T)
对于S SS的所有非空子集T TT,求f ( T ) f(T)f(T)的和,并对998244353 998244353998244353取模。
输入
输入包括N + 1 N+1N+1行
第一行一个正整数N NN,代表集合S SS共有N NN个点
接下来N NN行,每行两个空格隔开的正整数x i x_ixi和y i y_iyi,代表第i ii个点的坐标
数据范围
- 2 ≤ N ≤ 2 × 1 0 5 2leq Nleq 2 imes10^52≤N≤2×105
- − 1 0 9 ≤ x , y ≤ 1 0 9 -10^9leq x, yleq 10^9−109≤x,y≤109
- x i x_ixi各不相同
- y i y_iyi各不相同
输出
输出题目描述的结果。
例如:
集合S SS中共有3 33个点,坐标分别为( − 1 , 3 ) (-1,3)(−1,3)、( 2 , 1 ) (2,1)(2,1)和( 3 , − 2 ) (3,-2)(3,−2)
我们把这三个点记为P 1 P_1P1、P 2 P_2P2、P 3 P_3P3,则集合S = { P 1 , P 2 , P 3 } S={P_1,P_2,P_3}S={P1,P2,P3}
S SS共有7 77个非空子集
其中
- f ( { P 1 } ) = 1 f({P_1})=1f({P1})=1
- f ( { P 2 } ) = 1 f({P_2})=1f({P2})=1
- f ( { P 3 } ) = 1 f({P_3})=1f({P3})=1
- f ( { P 1 , P 2 } ) = 2 f({P_1,P_2})=2f({P1,P2})=2
- f ( { P 2 , P 3 } ) = 2 f({P_2,P_3})=2f({P2,P3})=2
- f ( { P 3 , P 1 } ) = 3 f({P_3,P_1})=3f({P3,P1})=3
- f ( { P 1 , P 2 , P 3 } ) = 3 f({P_1,P_2,P_3})=3f({P1,P2,P3})=3
因此答案是13 1313
样例输入 复制
3
-1 3
2 1
3 -2
样例输出 复制
13