首先将坐标系顺时针旋转45度，得到一个新的坐标系，这个坐标系
对应的坐标的manhattan距离就是原图中的距离，然后快排，利用前缀和
数组O（N）求所有的答案，然后找最小值就行了，总时间O(NlogN)，今天
体力不足，在此不再赘述。。。
/**************************************************************
Problem:
3170
User: BLADEVIL
Language: Pascal
Result: Accepted
Time:
860
ms
Memory:
19756
kb
****************************************************************/
//
By BLADEVIL
var
n :int64;
size :
array
[
0
..
2
,
0
..
500010
]
of
int64;
ans :
array
[
0
..
500010
]
of
int64;
sum :
array
[
0
..
500010
]
of
int64;
print :int64;
function
min(a,b:int64):int64;
begin
if
a>b
then
min:=b
else
min:=
a;
end
;
procedure
swap(
var
a,b:int64);
var
c :int64;
begin
c:
=a; a:=b; b:=
c;
end
;
procedure
init;
var
i :longint;
x, y :int64;
begin
read(n);
for
i:=
1
to
n
do
begin
read(x,y);
size[
1
,i]:=x+
y;
size[
2
,i]:=y-
x;
end
;
end
;
procedure
qs(low,high,s:int64);
var
i, j, xx :int64;
begin
i:
=low; j:=high; xx:=size[s,(i+j)
div
2
];
while
i<j
do
begin
while
size[s,i]<xx
do
inc(i);
while
size[s,j]>xx
do
dec(j);
if
i<=j
then
begin
swap(size[
1
,i],size[
1
,j]);
swap(size[
2
,i],size[
2
,j]);
swap(ans[i],ans[j]);
inc(i); dec(j);
end
;
end
;
if
i<high
then
qs(i,high,s);
if
j>low
then
qs(low,j,s);
end
;
procedure
main;
var
i :longint;
begin
qs(
1
,n,
1
);
for
i:=
1
to
n
do
sum[i]:=int64(size[
1
,i]);
for
i:=
1
to
n
do
sum[i]:=sum[i]+sum[i-
1
];
for
i:=
1
to
n
do
ans[i]:
=((i-
1
)*size[
1
,i]-sum[i-
1
])+((sum[n]-sum[i])-(n-i)*size[
1
,i]);
qs(
1
,n,
2
);
for
i:=
1
to
n
do
sum[i]:=int64(size[
2
,i]);
for
i:=
1
to
n
do
sum[i]:=sum[i]+sum[i-
1
];
for
i:=
1
to
n
do
ans[i]:
=ans[i]+((i-
1
)*size[
2
,i]-sum[i-
1
])+((sum[n]-sum[i])-(n-i)*size[
2
,i]);
print:
=maxlongint*
maxlongint;
for
i:=
1
to
n
do
print:=
min(print,ans[i]);
print:
=print
div
2
;
writeln(print);
end
;
begin
init;
main;
end
.
