QOJ.ac

QOJ

Time Limit: 12 s Memory Limit: 256 MB Total points: 100 Hackable ✓
[+33]

# 55. 欧几里得距离之和

Statistics

题目描述

给定平面上的 n 个点 (xi,yi), 定义 d(i,j)=(xixj)2+(yiyj)2, 求 1i<jnd(i,j).

输入格式

输入的第一行包含一个整数 n.

接下来 n 行, 每行两个整数 xi,yi.

输出格式

输出一行一个实数表示答案, 误差不超过 104

样例数据

样例输入

3
1 2
-1 3
0 -1

样例输出

9.5214512632858295782294770691381

样例解释

答案即为 d(1,2)+d(1,3)+d(2,3)=5+10+17

子任务

对于所有数据, 1n5×105,106xi,yi106.

  • Subtask 1(10 points): n3,000
  • Subtask 2(20 points): n40,000
  • Subtask 3(30 points): n105
  • Subtask 4(20 points): n3×105
  • Subtask 5(20 points): No additional constraints.