对一个点(x,y)定义x'=x+y,y'=x-y，曼哈顿距离就可以写成max(|x1'-x2'|,|y1'-y2'|)。
回到原题，容易发现，两个点(x1,y1)和(x2,y2)的距离为max(|x1-x2|,|y1-y2|)。
把上面的处理倒过来，就可以回到我们熟悉的曼哈顿距离了。
把点转换后枚举每个点，然后O(1)求出它到所有点的曼哈顿距离和。（排序后前缀和优化）。
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 410862 | lbz007 | 3170 | Accepted | 5696 kb | 696 ms | Pascal/Edit | 1487 B | 2013-05-13 07:13:26 |
1 var 2 p,q,sum,a,x,y:array[0..100000]of double; 3 b,rank:Array[1..100000]of longint; 4 ans,an,xx,yy:extended; 5 n,i,aa,bb:longint; 6 procedure sort(ll,rr:longint); 7 var 8 t,i,j:longint; 9 xx,tt:double; 10 begin 11 i:=ll;j:=rr; 12 xx:=a[ll+random(rr-ll+1)]; 13 while i<=j do 14 begin 15 while a[i]<xx do inc(i); 16 while a[j]>xx do dec(j); 17 if i<=j then 18 begin 19 tt:=a[i];a[i]:=a[j];a[j]:=tt; 20 t:=b[i];b[i]:=b[j];b[j]:=t; 21 inc(i);dec(j); 22 end; 23 end; 24 if ll<j then sort(ll,j); 25 if rr>i then sort(i,rr); 26 end; 27 function abs(xx:extended):extended; 28 begin 29 if xx>0 then exit(xx) 30 else exit(-xx); 31 end; 32 begin 33 readln(n); 34 for i:=1 to n do 35 begin 36 readln(aa,bb); 37 x[i]:=(aa+bb)/2; 38 y[i]:=(aa-bb)/2; 39 end; 40 a:=x; 41 for i:=1 to n do b[i]:=i; 42 sort(1,n); 43 for i:=1 to n do 44 sum[i]:=sum[i-1]+a[i]; 45 for i:=1 to n do 46 begin 47 p[b[i]]:=a[i]*(i-1)-sum[i-1]; 48 p[b[i]]:=p[b[i]]+sum[n]-sum[i]-a[i]*(n-i); 49 end; 50 ans:=9000000000000000; 51 a:=y; 52 for i:=1 to n do b[i]:=i; 53 sort(1,n); 54 sum[0]:=0; 55 for i:=1 to n do 56 sum[i]:=sum[i-1]+a[i]; 57 for i:=1 to n do 58 begin 59 q[b[i]]:=a[i]*(i-1)-sum[i-1]; 60 q[b[i]]:=q[b[i]]+sum[n]-sum[i]-a[i]*(n-i); 61 if q[b[i]]+p[b[i]]<ans then ans:=p[b[i]]+q[b[i]]; 62 end; 63 writeln(ans:0:0); 64 end.