1108 距离之和最小 V2

三维空间上有N个点, 求一个点使它到这N个点的曼哈顿距离之和最小，输出这个最小的距离之和。

点(x1,y1,z1)到(x2,y2,z2)的曼哈顿距离就是|x1-x2| + |y1-y2| + |z1-z2|。即3维坐标差的绝对值之和。

Input

第1行：点的数量N。(2 <= N <= 10000)
第2 - N + 1行：每行3个整数，中间用空格分隔，表示点的位置。（-10^9 <= X[i], Y[i], Z[i] <= 10^9)

Output

输出最小曼哈顿距离之和。

Input示例

Output示例

18


思路：求三个中位数

 1 #include <cctype>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 const int MAXN=10010;
 6 
 7 typedef long long LL;
 8 
 9 int n,Ax,Ay,Az;
10 
11 int x[MAXN],y[MAXN],z[MAXN];
12 
13 inline void read(int&x) {
14     int f=1;register char c=getchar();
15     for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
16     for(;isdigit(c);x=x*10+c-48,c=getchar());
17     x=x*f;
18 }
19 
20 inline LL abs(LL x) {return x<0?-x:x;}
21 
22 int hh() {
23     read(n);
24     for(register int i=1; i<=n; ++i) {
25         read(x[i]);read(y[i]);read(z[i]);
26         Ax+=x[i];Ay+=y[i],Az+=z[i];
27     }
28     
29     std::sort(x+1,x+1+n);
30     std::sort(y+1,y+1+n);
31     std::sort(z+1,z+1+n);
32     int mid;
33     Ax=x[(n+1)>>1],Ay=y[(n+1)>>1],Az=z[(n+1)>>1];
34     LL ans=0;
35     for(int i=1; i<=n; ++i) 
36       ans+=(LL)abs((LL)Ax-x[i])+abs((LL)Ay-y[i])+abs((LL)Az-z[i]);
37     
38     printf("%lld
",ans);
39     
40     return 0;
41 }
42 
43 int sb=hh();
44 int main(int argc,char**argv) {;}

代码