E. Points

Codeforces

IDCF76E

Time1000ms

Memory256MB

Difficulty—

implementationmath

English · Original

Chinese · Translation

Formal · Original

You are given _N_ points on a plane. Write a program which will find the sum of squares of distances between all pairs of points. ## Input The first line of input contains one integer number _N_ (1 ≤ _N_ ≤ 100 000) — the number of points. Each of the following _N_ lines contain two integer numbers _X_ and _Y_ ( - 10 000 ≤ _X_, _Y_ ≤ 10 000) — the coordinates of points. Two or more points may coincide. ## Output The only line of output should contain the required sum of squares of distances between all pairs of points. [samples]

给定平面上的 #cf_span[N] 个点。编写一个程序，求所有点对之间距离的平方和。输入的第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 100 000]) —— 点的数量。接下来的 #cf_span[N] 行每行包含两个整数 #cf_span[X] 和 #cf_span[Y] (#cf_span[ - 10 000 ≤ X, Y ≤ 10 000]) —— 点的坐标。可能存在两个或更多重合的点。输出仅一行，包含所有点对之间距离的平方和。 ## Input 输入的第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 100 000]) —— 点的数量。接下来的 #cf_span[N] 行每行包含两个整数 #cf_span[X] 和 #cf_span[Y] (#cf_span[ - 10 000 ≤ X, Y ≤ 10 000]) —— 点的坐标。可能存在两个或更多重合的点。 ## Output 输出仅一行，包含所有点对之间距离的平方和。 [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of points. Let $ P = \{ p_i = (x_i, y_i) \mid i \in \{1, \dots, N\} \} $ be the set of points in $ \mathbb{R}^2 $, where $ x_i, y_i \in \mathbb{Z} $. **Constraints** 1. $ 1 \leq N \leq 100{,}000 $ 2. $ -10{,}000 \leq x_i, y_i \leq 10{,}000 $ for all $ i \in \{1, \dots, N\} $ **Objective** Compute the sum of squared Euclidean distances between all unordered pairs of distinct points: $$ \sum_{1 \leq i < j \leq N} \left( (x_i - x_j)^2 + (y_i - y_j)^2 \right) $$

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "E. Points",
    "description": {
      "content": "You are given _N_ points on a plane. Write a program which will find the sum of squares of distances between all pairs of points.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF76E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given _N_ points on a plane. Write a program which will find the sum of squares of distances between all pairs of points.\n\n## Input\n\nThe first line of input contains one integer number _N_ (1 ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定平面上的 #cf_span[N] 个点。编写一个程序，求所有点对之间距离的平方和。\n\n输入的第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 100 000]) —— 点的数量。接下来的 #cf_span[N] 行每行包含两个整数 #cf_span[X] 和 #cf_span[Y] (#cf_span[ - 10 000 ≤ X, Y ≤ 10 000]) —— ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of points.  \nLet $ P = \\{ p_i = (x_i, y_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of points in $ \\mathbb{R}^2 $, where $ x_i, y_i \\in \\math...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments