No.3530 「」
タグ : / 解いたユーザー数 8
作問者 :
Germanium32
Problem Statement
There are $N$ points $1,\dots ,N$ on a plane. The coordinates of point $i$ are $(x_i,y_i)$.
The following operation is applied once to each point.
- Choose $s_i$ to be one of $0,90,180,270$, and draw the $2$ segments obtained by rotating the segment connecting $(x_i,y_i)$ and $(x_i+0.5,y_i)$ counterclockwise around $(x_i,y_i)$ by $s_i,s_i+90$ degrees.
After that, the following operation is repeated until there are no new parts to paint or it can no longer be performed.
-
Choose distinct points $i,j$ with $1\leq i,j\leq N$ such that the drawn segments form the shape of 「」 (corner brackets), and paint the inside.
- More strictly, choose distinct integers $i,j$ satisfying $x_i\lt x_j$ and $y_i\gt y_j$ as well as $s_i=270,s_j=90$, and fill the rectangle having $(x_i,y_i),(x_i,y_j),(x_j,y_j),(x_j,y_i)$ as its vertices.
Find the sum, over all $4^N$ ways, of the total perimeter (including holes) of the finally painted region, $\mod 998244353$.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $-10^9 \leq x_i, y_i \leq 10^9$
- All input values are integers.
Input
$N$ $x_1\ y_1$ $\vdots$ $x_N\ y_N$
Output
Print a newline at the end.
Sample
Sample 1
Input
2 1 1 3 0
Output
6
The perimeter is $6$ only when $s_1=270, s_2=90$, as shown below; in all other cases the perimeter is $0$.
Sample 2
Input
10 -9570757 -8684416 -86136813 2285372 -47853785 -4113671 -9570757 -8684416 -66995299 -1371224 66995299 -2285373 -86136813 457074 -9570757 -7770267 -28712271 4113670 -86136813 457074
Output
591562628
Print the value taken $\mod 998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。