問題一覧 > 通常問題

No.1649 Manhattan Square

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 48
作問者 : MitarushiMitarushi / テスター : 蜜蜂蜜蜂 👑 ygussanyygussany
2 ProblemId : 6791 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-05 10:46:54

問題文

$N$ 個の二次元平面上の点が与えられ、$i$ 番目の点 $p_i$ の座標は $(x_i, y_i)$ です。
全ての $2$ 点の組のマンハッタン距離の二乗の和を $\bmod 998244353$ で求めてください。つまり以下の値を出力してください。
\[ \left( \sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \left(|x_i - x_j| + |y_i - y_j|\right)^2 \right) \bmod 998244353 \]

入力

$N$
$x_1\ \ y_1$
$x_2\ \ y_2$
$\vdots$
$x_N\ \ y_N$

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq x_i, y_i \leq 10^9\ (1 \leq i \leq N)$
  • $(x_i, y_i)$ は相異なる
  • 入力は全て整数

    • 出力

    答えを出力し、最後に改行してください。

    サンプル

    サンプル1
    入力
    3
    20 21
    8 13
    21 20
    出力
    804

    • $p_1$ と $p_2$ のマンハッタン距離は $|20-8|+|21-13|=20$ です。
    • $p_1$ と $p_3$ のマンハッタン距離は $|20-21|+|21-20|=2$ です。
    • $p_2$ と $p_3$ のマンハッタン距離は $|8-21|+|13-20|=20$ です。
    よって、答えは $20^2+2^2+20^2=804$ となります。

    サンプル2
    入力
    10
    820452084 718229520
    553492242 206036568
    836505501 213104158
    629890367 87785981
    743726641 227761681
    179932548 523018260
    617059779 887083076
    857634650 10893928
    540244583 891972563
    122356429 76481779
    出力
    404638485

    $\bmod 998244353$ で求めてください。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。