問題一覧 > 通常問題

No.1649 Manhattan Square

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 49
作問者 : Mitarushi / テスター : 蜜蜂 ygussany
お気に入りにしたユーザー ProblemId : 6791 / 自分の提出
問題文最終更新日: 2021-08-05 10:46:54
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
yukicoder contest 309 (順位表) の他の問題:

Problem Statement

You are given $N$ points on a two-dimensional plane. The coordinates of the $i$-th point $p_i$ are $(x_i, y_i)$.
Find the sum of the squares of the Manhattan distances over all pairs of $2$ points, modulo $\bmod 998244353$. In other words, output the following value.
\[ \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 \]

Input

$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)$ are pairwise distinct
  • All inputs are integers

    • Output

    Output the answer, followed by a newline.

    Sample

    Sample 1
    Input
    3
    20 21
    8 13
    21 20
    Output
    804

    • The Manhattan distance between $p_1$ and $p_2$ is $|20-8|+|21-13|=20$.
    • The Manhattan distance between $p_1$ and $p_3$ is $|20-21|+|21-20|=2$.
    • The Manhattan distance between $p_2$ and $p_3$ is $|8-21|+|13-20|=20$.
    Therefore, the answer is $20^2+2^2+20^2=804$.

    Sample 2
    Input
    10
    820452084 718229520
    553492242 206036568
    836505501 213104158
    629890367 87785981
    743726641 227761681
    179932548 523018260
    617059779 887083076
    857634650 10893928
    540244583 891972563
    122356429 76481779
    Output
    404638485

    Find the answer modulo $\bmod 998244353$.

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