🐷大肚肚
CF-76E3

距离

⏱ 1.0s💾 256MB

📋 题目描述

给定平面上的 nn 个点及其它们在平面直角坐标系中的坐标,请你计算所有点对之间距离的平方和。

📥 输入格式

第一行仅有一个整数 nn ( 1≤n≤1051\le n \le 10^5 )表示点的个数,接下来的 nn 行,每行包含两个整数 x,yx,y ( −104≤x,y≤104-10^4\le x,y \le 10^4 )给出一个点的横纵坐标,可能有两个或多个点坐标重合的情况。

📤 输出格式

仅有一个数,表示所有点对之间距离的平方和。

📝 样例 1

输入
4
1 1
-1 -1
1 -1
-1 1
输出
32

💡 题目讲解

1

理解题意

给定平面上 nn 个点,求所有点对之间距离的平方和。

距离公式:两点 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 的距离平方 = (x1−x2)2+(y1−y2)2(x_1-x_2)^2 + (y_1-y_2)^2。

n≤105n \le 10^5,不能枚举所有点对(O(n2)=1010O(n^2)=10^{10} 太大了)。


以 4 个点为例:(1,1),(−1,−1),(1,−1),(−1,1)(1,1),(-1,-1),(1,-1),(-1,1)。四个点形成正方形,点对共 6 对。

直接算:(1,1)(1,1) 到 (−1,1)(-1,1) 距离平方 = (1−(−1))2+(1−1)2=4(1-(-1))^2+(1-1)^2=4……6 对全加起来 = 32。

1 / 5