Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
神の使いであるMMNMMさんは,夏祭りの騒ぎで悪霊が住み着かないように境内に結界を張ることにしました.
境内には N 個の灯籠があり, i 個目の灯籠は座標 (X_{i},Y_{i}) に存在します.同じ座標に二つの灯籠が存在することはありません.
MMNMMさんは以下の2つの結界の貼り方を好きな順番で何回でも行うことができます.
- 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}
- 1行目には整数 N が書かれている.これは,神社の境内に存在する灯籠の個数を表している.
- 続く N 行のうちの i 行目には二つの整数 X_{i} と Y_{i} が空白区切りで書かれている.これは i 番目の灯籠が座標 (X_{i},Y_{i}) に存在することを示している.
出力
標準出力に結界の長さの総和を出力しなさい.
入力例 1
3 0 0 1 2 2 0
出力例 1
4
- 1番目の灯籠と3番目の灯籠は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
結界を張ることができない灯籠の位置が存在することにも注意しなさい.