2314314_ac_359ms_2400k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 51 行

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

long n;
int u[max], v[max], w[max];

bool cmp(long a,long b)
{
	return a>b;
}

int input()
{
	long m, i, j, k;
	__int64 t1, t2, t3, ans = 0;

	scanf("%ld",&n);
	if(!n)
		return 0;
	for(m = 0; m < n; m++)
	{
		scanf("%ld%ld%ld",&i,&j,&k);
		u[m] = i-j;v[m] = j-k;w[m] = k-i;
	}
	sort(u,u+n,cmp);sort(v,v+n,cmp);sort(w,w+n,cmp);
	ans += u[0]-u[1];
	t1 = ans;
	ans += v[0] - v[1];
	t2 = v[0] - v[1];
	ans += w[0] - w[1];
	t3 = w[0] - w[1];
	for(i = 2; i < n; i ++)
	{
		t1 += i*(u[i-1] - u[i]);
		ans += t1;
		t2 += i*(v[i-1] - v[i]);
		ans += t2;
		t3 += i*(w[i-1] - w[i]);
		ans += t3;
	}
	printf("%I64d\n",ans/2);
	return 1;
}

int main()
{
	while(input());
	return 1;
}