🐷大肚肚
CF-76E3

距离

1.0s💾 256MB

📋 题目描述

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

📥 输入格式

第一行仅有一个整数 nn1n1051\le n \le 10^5 )表示点的个数,接下来的 nn 行,每行包含两个整数 x,yx,y104x,y104-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) 的距离平方 = (x1x2)2+(y1y2)2(x_1-x_2)^2 + (y_1-y_2)^2

n105n \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+(11)2=4(1-(-1))^2+(1-1)^2=4……6 对全加起来 = 32。

1 / 5