UOJ Logo LFYZ Online Judge

LFYZOJ

#9. 童游

统计

拙いものと思えども、

その手に握る其れこそが、

いつか幻想を生んでいく。

虽然尚显笨拙,

但此刻他们手握之物,

终有一日,会将幻想孕育。

——童遊 めらみぽっぷ

问题描述

一天,幻想乡内的少女们决定去参加八云紫的宴会。

她们分散在一个很大很大的方阵上。且每位少女都在格点上。由于紫有隙间,因此只要少女们聚集到一个点上,紫就可以把她们全部接走啦。

因此,少女们想让你算出她们聚集到同一个点的最短距离和。

注意:少女们只能沿着方阵的网格走,不可滑翔、瞬移、开摩托横冲直撞等。

输入格式

第一行是一个整数 $n$ ,代表有多少位少女。

下来 $n$ 行一行两个整数 $x$ 与 $y$ ,代表每位少女的横坐标与纵坐标。

输出格式

一个整数,是你给出的答案。

样例一

input

4
1 1
2 3
4 6
8 10

output

21

explanation

如图所示,其中红点代表少女,绿点代表聚集到一起的点,黑边代表走的路径。

示意图

数据范围与约定

对于 $30\%$ 的数据,保证所有的纵坐标都相等,$n \leq 100$。

对于另外 $20\%$ 的数据,保证每一位少女的横坐标等于她的纵坐标,$n \leq 100$。

对于上述 $50\%$ 的数据,保证所有少女横纵坐标均在 $[1,800]$ 内。

对于 $100\%$ 的数据,若有 $i < j$ ,则保证,$x_i \leq x_j $ ,$y_i \leq y_j$。$n \leq 100000$。

保证所有少女横纵坐标均在$[1,100000]$内。少女可能重叠。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$

下载

样例数据下载

  • ex_aso1.in/out 对应样例。

  • ex_aso2.in/out 对应 $50\%$ 的数据范围。

  • ex_aso3.in/out 对应 $100\%$ 的数据范围。