怎样加快网站收录,哈尔滨网站只做,深圳高端网站制作公司排名,海口仿站定制模板建站城市距离之和 内存限制: 256 Mb时间限制: 1000 ms
题目描述
设 (x,y)(x,y) 与 (x′,y′)(x′,y′) 是平面上的两个点的坐标#xff0c;它们之间的城市距离定义为
∣x−x′∣∣y−y′∣∣x−x′∣∣y−y′∣
给定 nn 个点#xff0c;请计算所有点对之间的城市距离之和。
… 城市距离之和 内存限制: 256 Mb时间限制: 1000 ms
题目描述
设 (x,y)(x,y) 与 (x′,y′)(x′,y′) 是平面上的两个点的坐标它们之间的城市距离定义为
∣x−x′∣∣y−y′∣∣x−x′∣∣y−y′∣
给定 nn 个点请计算所有点对之间的城市距离之和。
输入格式
第一行单个整数 nn。第二行到第 n1n1 行第 i1i1 行有两个整数 xixi 和 yiyi表示一个点的坐标。
输出格式
单个整数表示所有点对的城市距离之和。
数据范围
30%30% 的数据1≤n≤10001≤n≤100060%60% 的数据1≤n≤500001≤n≤50000100%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
题解
#includebits/stdc.h
using namespace std;
const int N300005;
long long x[N],y[N],sum,n,k;
int main(){cinn;for(int i0;in;i){cinx[i]y[i];}sort(x,xn);sort(y,yn);for(int in-1,kn-1;i0;i--,k-2){sumk*x[i];sumk*y[i];}coutsum;return 0;
}
