首先將坐標系順時針旋轉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
.
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
