2286632_wa.cpp

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

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

long n;
struct node
{
	long id;
	long x, y;
}wel[100001];
long 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()
{
	long i;
	long x, y, tmp;
	long sumx = 0, sumy = 0;
	long res[100001];

	scanf("%ld",&n);
	for(i = 0; i < n; i++)
	{
		scanf("%ld%ld",&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;
	}
	long min = 2100000000;
	for(i = 0; i < n; i++)
		if(res[i]<min)
			min = res[i];
	printf("%ld\n",min/2);
	return 1;
}