#P17825. [Ontak2022]GOC

    ID: 16768 传统题 500~5000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>数据结构计算几何CF2400线段树排序算法基础模拟

[Ontak2022]GOC

题目描述

平面上有 nn 枚硬币,第 ii 枚位于 (xi,yi)(x_i,y_i)。你控制一名携带特殊磁铁的角色,初始位于 (0,0)(0,0)。

角色每次可以向上、下、左、右移动一个单位。磁铁会立即吸走所有与角色当前位置具有相同横坐标或相同纵坐标的硬币。

求吸走全部硬币需要移动的最短总距离,不要求返回起点。

输入格式

第一行一个整数 nn。接下来 nn 行,每行两个整数 xi,yix_i,y_i。

输出格式

输出最短总距离。

数据范围

1≤n≤5000001\le n\le500000;−109≤xi,yi≤109-10^9\le x_i,y_i\le10^9。原题没有要求硬币坐标互不相同。

子任务

子任务 附加限制 分值
1 n≤200 8
2 n≤5000 10
3 所有 xᵢ,yᵢ≥0 9
4 所有 xᵢ≥0 16
5 无额外限制 57

样例 1

输入:

11
2 2
1 8
8 2
7 -3
1 -1
-1 -2
-2 -1
-5 -1
-6 1
-2 2
-1 3

输出:

10