上海市计算机学会竞赛平台2024年5月月赛丙组城市距离之和
城市距离之和
内存限制: 256 Mb时间限制: 1000 ms
题目描述
设 (x,y)(x,y) 与 (x′,y′)(x′,y′) 是平面上的两个点的坐标，它们之间的城市距离定义为
∣x−x′∣+∣y−y′∣∣x−x′∣+∣y−y′∣
给定 nn 个点，请计算所有点对之间的城市距离之和。
输入格式
- 第一行：单个整数 nn。
- 第二行到第 n+1n+1 行：第 i+1i+1 行有两个整数 xixi 和 yiyi，表示一个点的坐标。
输出格式
- 单个整数：表示所有点对的城市距离之和。
数据范围
- 30%30% 的数据，1≤n≤10001≤n≤1000
- 60%60% 的数据，1≤n≤500001≤n≤50000
- 100%100% 的数据，1≤n≤300,0001≤n≤300,000
- −106≤xi,yi≤106−106≤xi,yi≤106
样例数据
输入:
3
1 1
2 3
1 4
输出:
8
说明:
3 + 3 + 2 = 8
题解：
#include<bits/stdc++.h>
using namespace std;
const int N=300005;
long long x[N],y[N],sum,n,k;
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
}
sort(x,x+n);
sort(y,y+n);
for(int i=n-1,k=n-1;i>=0;i--,k-=2){
sum+=k*x[i];
sum+=k*y[i];
}
cout<<sum;
return 0;
}