D: Built? - AtCoder Regular Contest 076
座標(x[i], y[i])に街がある、街間に道路を引くためにはx座標の差またはy座標の差の小さいほうの距離だけコストがかかる。いくつか道路を引いて全部の街を行き来できるようにするための最小コストはいくつか？
最小全域木を求めれば良いのでKruskal法またはPrim法をする。ただし、全部の街の間にEdgeを引くと計算量がオーバーする。具体的にはO(N^2 logN)になる。
そのため、あらかじめx座標でソートした街、y座標でソートした街を作成しておき、その前後でしかEdgeがないようにしておくと、Edgeの数は(N-1)*2に抑えられる。そのため計算量がO(N logN)で計算できる。
