C语言的技术，求 Hyperspace

Question

Problem Description
The great Mr.Smith has invented a hyperspace particle generator. The device is very powerful. The device can generate a hyperspace. In the hyperspace, particle may appear and disappear randomly. At the same time a great amount of energy was generated.
However, the device is in test phase, often in a unstable state. Mr.Smith worried that it may cause an explosion while testing it. The energy of the device is related to the maximum manhattan distance among particle.
Particles may appear and disappear any time. Mr.Smith wants to know the maxmium manhattan distance among particles when particle appears or disappears.

Input
The input contains several test cases, terminated by EOF.
In each case: In the first line, there are two integer q(number of particle appear and disappear event, ≤60000) and k(dimensions of the hyperspace that the hyperspace the device generated, ≤5). Then follows q lines. In each line, the first integer ‘od’ represents the event: od = 0 means this is an appear
event. Then follows k integer(with absolute value less then 4 × 107). od = 1 means this is an disappear event. Follows a integer p represents the disappeared particle appeared in the pth event.

Output
Each test case should contains q lines. Each line contains a integer represents the maximum manhattan distance among paticles.

Sample Input
10 2
0 208 403
0 371 -180
1 2
0 1069 -192
0 418 -525
1 5
1 1
0 2754 635
0 -2491 961
0 2954 -2516

Sample Output
0
746
0
1456
1456
1456
0
2512
5571
8922

Answer 1

Problem Description
Hyperspace ,A Euclidean space of dimension greater than three (the original meaning of the word hyperspace, common in late nineteenth century British books, sometimes used in paranormal context, but which has become rarer since then). Minkowski space, a concept, often referred to by science fiction writers as hyperspace that refers to the four-dimensional space-time of special relativity.

Here we define a “Hyperspace” as a set of points in three-dimensional space. We define a function to describe its “Hyperspace Value”

Every vi (0<=i<=k) could be describe in three-dimensional reference system, say v0 (1, 2, 3)
For the following question, we will have to deal with the “Hyperspaces”, you may assume that the number of “Hyperspace” is always no larger than 100.
As we say above, we give every “Hyperspace” an “ID” to identify it.
If you want to connect two points in two different “Hyperspaces”, it will cost you F to build the connection. F can be defined as the following expression:

In addition, you can only create at most one connection between any two “Hyperspaces”.
If you want to connect two points in the same “Hyperspaces” whose “ID” is k, it will cost you G to build the connection. G can be defined as the following expression:

Here

Now your task is quite easy.
AekdyCoin gives you n “Hyperspaces”.
Then he gives you information about all the points in the “Hyperspaces”
Now he wants to know the minimal cost to connect all the points in all “Hyperspaces”

you have to ensure that any two different points in the same "Hyperspace" could be connected directly or indirectly by the connections you build in this "Hyperspace".

Input
The input consists of several test cases.
In the first line there is an integer n (1<=n<=100), indicating the number of “Hyperspaces”
Then follow an integer m (1<=m<=100000)
You can assume that the number of different points in every “Hyperspace” is always no larger than 100.
The next m lines contain the descriptions of all the points
All the descriptions are given in the following format x,y,z,id
Indicating the point (x,y,z) belongs to the id “Hyperspace”
id is an integer.
x,y,z are all real number with at most four fractional digits.
-10000<=x,y,z<=10000,1<=id<=n

Output
For each test case, output the minimal cost on a single line.
Please round it to four fractional digits.

Sample Input
1
2
1 2 1 1
1 3 1 1

Sample Output
1.0000