← 返回题目列表

AtCoder · summerfes2018_j

J. 制作障碍很有趣

中文机器翻译题面 查看原题

配点 : 200 点

問題文

MMNMM先生是上帝的使者,他决定在寺庙内设置屏障,以防止邪灵因夏季节日的骚动而定居。

在辖区内 有 N 灯笼, i 灯笼的坐标 它存在于 (X_{i},Y_{i}) 中。两个灯笼不能存在于同一坐标处。

MMNMM 可以根据需要以任何顺序多次应用以下两种屏障方法。

  • 在端点为具有相同 X 或 Y 坐标的两个灯笼的线段上创建障碍。
  • 对于已经存在的障碍物和灯笼,从灯笼到该障碍物放置一条垂直线,如果其脚在障碍物上,则在连接灯笼和垂直线脚的线段上绘制一个新的障碍物。

MMNMM先生试图通过上述两个操作来尽可能地增加障碍物所附着的线段的长度总和。 (请注意,如果两个不同的边界共享同一线段,则重叠部分的长度不会多次相加。详细信息请参见输入/输出示例的说明。)

N 灯笼的坐标,编写一个程序来计算穿过 MMNMM 可以创建的边界的线段的长度总和。

制約

所有测试用例都满足以下约束。

  • 2 \leq N \leq 200000
  • -1000000000 \leq X_{i},Y_{i} \leq 1000000000 (1 \leq i \leq N)
  • i \neq j 如果 X_{i} \neq X_{j} 或 Y_{i} \neq Y_{j}

入力

输入是按以下格式从标准输入给出的。

N
X_{1} Y_{1}    
X_{2} Y_{2}    
:
X_{N} Y_{N}
  • 第一行是一个整数 写入 N 。这代表神社境内存在的灯笼数量。
  • 继续 N 行 i 行有两个整数 X_{i} 和 Y_{i} 用空格分隔。这是 i 第一个灯笼是坐标 它表明它存在于 (X_{i},Y_{i}) 中。

出力

将障碍物的总长度输出到标准输出。


入力例 1

3
0 0
1 2
2 0

出力例 1

4
  1. 第一个灯笼和第三个灯笼具有相同的 Y 坐标,因此 MMNMM 具有坐标 您可以在以 (0,0) 和 (2,0) 作为终点的线段上创建障碍。
  2. 从第二个灯笼画到 1. 中拉伸的障碍物的垂直线的底部存在于 1. 中拉伸的障碍物上,因此 MMNMM 可以计算出坐标。 (1,0) 和 (1,2) 作为终点的线段上创建障碍。

由于不可能在任何其他位置创建屏障,因此所需屏障长度的总和为 2+2=4。


入力例 2

5
1 1
4 3
1 3
2 2
3 1

出力例 2

13

最后,将在如图所示的直线组上放置障碍物。


入力例 3

4
123 456
789 12
345 678
901 234

出力例 3

0

另请注意,有些灯笼位置无法创建障碍。