問題一覧 > 通常問題

No.3530 「」

レベル : / AI推定難易度 : 2800 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : aa36 / テスター : Yoyoyo8128 yu23578 Germanium32 GaLLium
お気に入りにしたユーザー ProblemId : 13118 / 自分の提出
問題文最終更新日: 2026-05-04 21:13:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
聖光学院プログラミングコンテスト2026 day2 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。