2286640_ac_1028ms_3168k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>
using namespace std;

__int64 n;
struct node
{
	__int64 id;
	__int64 x, y;
}wel[100001];
__int64 res[100001];

bool X(struct node a,struct node b)
{
	return a.x<b.x;
}

bool Y(struct node a,struct node b)
{
	return a.y<b.y;
}

int main()
{
	__int64 i;
	__int64 x, y, tmp;
	__int64 sumx = 0, sumy = 0;
	__int64 res[100001];

	scanf("%I64d",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%I64d%I64d",&x,&y);
		wel[i].x = x-y;
		wel[i].y = x+y;
		wel[i].id = i;
		sumx += wel[i].x;
		sumy += wel[i].y;
	}
	sort(wel,wel+n,X);
	memset(res,0,sizeof(res));
	tmp = 0;
	for(i = 0; i < n; i++)
	{
		sumx -= wel[i].x;
		res[wel[i].id] += sumx-(n-i-1)*wel[i].x+i*wel[i].x-tmp;
		tmp += wel[i].x;
	}
	sort(wel,wel+n,Y);
	tmp = 0;
	for(i = 0; i < n; i++)
	{
		sumy -= wel[i].y;
		res[wel[i].id] += sumy-(n-i-1)*wel[i].y+i*wel[i].y-tmp;
		tmp += wel[i].y;
	}
	__int64 min = 210000000000;
	for(i = 0; i < n; i++)
		if(res[i]<min)
			min = res[i];
	printf("%I64d\n",min/2);
	return 1;
}