#P2177. 曼哈顿最小生成树

    ID: 1200 传统题 1000ms 512MiB 尝试: 350 已通过: 108 难度: 8 上传者: 标签>CF2400提高+/省选-最小生成树候选边稀疏化坐标变换扫描线离散化树状数组交换论证Kruskal普通并查集

曼哈顿最小生成树

题目描述

平面坐标系 xOy\text{xOy} 内,给定 nn 个顶点 (xi,yi)(x_i , y_i) 。对于顶点 u,vu,v,uu 与 vv 之间的距离 dd 定义为 ∣xu−xv∣+∣yu−yv∣|x_u - x_v| + |y_u - y_v|。

你的任务就是求出这 nn 个顶点的最小生成树。

输入格式

第一行一个正整数 nn,表示定点个数。

接下来 nn 行每行两个正整数 x,yx,y,描述一个顶点。

输出格式

只有一行,为最小生成树的边的距离和。

样例输入

4
1 0
0 1
0 -1
-1 0

样例输出

6

数据规模与约定

对于 100%100\% 的数据,n≤5×104n\leq 5\times 10^4,0≤x,y≤1×1050\leq x,y\leq 1\times 10^5。