Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Difference between Triplets
Description For every pair of triplets, I, _{a}J, _{a}K) and _{a}T_{b }= (I, _{b}J,_{b} K), we define the _{b}difference value between T and _{a}T_{b }as follows:
T) = max {_{b}I − _{a} I, _{b}J − _{a}J, _{b}K − _{a}K} − min {_{b}I − _{a} I, _{b}J − _{a}J, _{b}K − _{a}K}_{b}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}T. Then, there are following _{N}N lines, each line contains three integers, giving the elements of each triplet.
A case with N = 0 indicates the end of the input.
Output For each case, output a line with the sum of difference values between every unordered pair of triplets. 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)=4
_{2}Case 2: D(T,_{1}T)+_{2}D(T,_{1}T)+_{3}D(T,_{2}T)=8+8+4=20
_{3}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. Source POJ Monthly--2007.07.08, Yuan, Xinhao |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator