# POJ 3244 Difference between Triplets 题解：（线段树或树状数组）或（排序 + 前缀和）

|

## Description

For every pair of triplets, $T_a = (I_a, J_a, K_a)$ and $T_b = (I_b, J_b, K_b)$, we define the difference value between $T_a$ and $T_b$ as follows:

$$D(T_a, T_b) = \max (I_a − I_b, J_a − J_b, K_a − K_b) − \min (I_a − I_b, J_a − J_b, K_a − K_b)$$

Now you are given $N$ triplets, could you write a program to calculate the sum of the difference values between every unordered pair of triplets?

## Input

The input consists of several test cases.
Each test case begins with a line containing an integer $N$, denotes the number of triplets. Assume that we number the triplets as $T_1, T_2, \dots , T_N$. Then, there are following $N$ lines, each line contains three integers, giving the elements of each triplet.
A case with $N = 0$ indicates the end of the input.

## Sample Input

2
1 2 3
3 2 1
3
1 3 2
4 0 7
2 2 9
0

## Sample Output

4
20

## Hint

Case 1: $D(T_1,T_2)=4$
Case 2: $D(T_1,T_2)+D(T_1,T_3)+D(T_2,T_3)=8+8+4=20$

You can assume that $N$, the number of triplets in each case, will not exceed 200,000 and the elements in triplets fit into $[-10^6,10^6]$.
The size of the input will not exceed 5 MB.

## Analysis

### Solutoin #1

$$I_a-I_b>J_a-J_b,I_a-I_b>K_a-K_b$$

$$I_a-J_a>I_b-J_b,I_a-K_a-i_b-K_b$$

### Solution #2

$$\max(a,b,c)-\min(a,b,c) = \frac {|a-b|+|b-c|+|c-a|} 2$$

$$D(T_a, T_b) = \max (I_a − I_b, J_a − J_b, K_a − K_b) − \min (I_a − I_b, J_a − J_b, K_a − K_b) \\ = \frac {|I_a-I_b-J_a+J_b| + |J_a-J_b-K_a-K_b| + |K_a-K_b-I_a+I_b|} 2$$

$$D(T_a,T_b)=\frac {|A_a-A_b|+|B_a-B_b|+|C_a-C_b|} 2$$

$$\sum D(T_i,T_j) = \frac {\sum_{A_i< A_j} (A_j-A_i) +\sum_{C_i< C_j} (C_j-C_i) + \sum_{C_i< C_j} (C_j-C_i) } {2}$$

## Code

\下面是解法二的代码。POJ 这题提交的时候如果语言选择 G++ 会 WA 掉，但是用 C++ 就过了……困扰了我很长时间……

Prior to the compiler upgrade in May 2009, we serviced C and C++ submissions using GCC 3.4.2. That version of GCC relies on the old MS VC++ 6 runtime library, which does not support the %lld and %llu specifiers for signed and unsigned long long types but allows the standard-incompliant %lf and %lg specifiers for floating-point types. The new GCC 4.4.0 comes with its own ISO C-conformant implementation of the printf function. Now you can use %lld and %llu with either C/C++ compiler, but %lf and %lg only work with MS VC++ 2008 Express. As a rule of thumb, you should always use the %f and %g specifiers instead for floating-point types.

…可怕……

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const long long maxn=200005;
long long n,a[maxn],b[maxn],c[maxn];
long long ans=0;

int main(){
for (;;){
scanf("%lld",&n);
if (n==0) break;
ans=0;

for (long long i=1;i<=n;i++){
long long x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
a[i]=x-y,b[i]=y-z,c[i]=z-x;
}
sort(a+1,a+1+n);sort(b+1,b+1+n);sort(c+1,c+1+n);

long long sum_a=0,sum_b=0,sum_c=0;
for (long long i=1;i<=n;i++){
ans+=a[i]*(i-1)-sum_a;
ans+=b[i]*(i-1)-sum_b;
ans+=c[i]*(i-1)-sum_c;
sum_a+=a[i];sum_b+=b[i];sum_c+=c[i];
}
printf("%lld\n",ans/2);
}
return 0;
}