10742: ABC136 - F - Enclosed Points
[Creator : ]
Description
We have a set $S$ of $N$ points in a two-dimensional plane. The coordinates of the $i$-th point are $(x_i, y_i)$. The $N$ points have distinct $x$-coordinates and distinct $y$-coordinates.
For a non-empty subset $T$ of $S$, let $f(T)$ be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in $T$. More formally, we define $f(T)$ as follows:
- $f(T) := $ (the number of integers $i$ $(1 \leq i \leq N)$ such that $a \leq x_i \leq b$ and $c \leq y_i \leq d$, where $a$, $b$, $c$, and $d$ are the minimum $x$-coordinate, the maximum $x$-coordinate, the minimum $y$-coordinate, and the maximum $y$-coordinate of the points in $T$)
Find the sum of $f(T)$ over all non-empty subset $T$ of $S$. Since it can be enormous, print the sum modulo $998244353$.
For a non-empty subset $T$ of $S$, let $f(T)$ be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in $T$. More formally, we define $f(T)$ as follows:
- $f(T) := $ (the number of integers $i$ $(1 \leq i \leq N)$ such that $a \leq x_i \leq b$ and $c \leq y_i \leq d$, where $a$, $b$, $c$, and $d$ are the minimum $x$-coordinate, the maximum $x$-coordinate, the minimum $y$-coordinate, and the maximum $y$-coordinate of the points in $T$)
Find the sum of $f(T)$ over all non-empty subset $T$ of $S$. Since it can be enormous, print the sum modulo $998244353$.
Input
Input is given from Standard Input in the following format:
```
$N$
$x_1$ $y_1$
$:$
$x_N$ $y_N$
```
```
$N$
$x_1$ $y_1$
$:$
$x_N$ $y_N$
```
Output
Print the sum of $f(T)$ over all non-empty subset $T$ of $S$, modulo $998244353$.
Constraints
- $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)$
- All values in input are integers.
- $-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)$
- All values in input are integers.
Sample 1 Input
3
-1 3
2 1
3 -2
Sample 1 Output
13
Let the first, second, and third points be $P_1$, $P_2$, and $P_3$, respectively. $S = \{P_1, P_2, P_3\}$ has seven non-empty subsets, and $f$ has the following values for each of them:
- $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$
The sum of these is $13$.
Sample 2 Input
4
1 4
2 1
3 3
4 2
Sample 2 Output
34
Sample 3 Input
10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6
Sample 3 Output
7222