#include "bits/stdc++.h" using namespace std; #define ll long long #define ppp pair, int> set xg, yg; map> xii, yii; ppp expand_ppp(ppp a, ppp b) { return { { max(a.first.first, b.first.first), min(a.first.second, b.first.second) }, a.second }; } void add_node(ppp xp, ppp yp) { int iy = -1, ix = -1; cout << xp.first.first << '-' << yp.first.first << ' ' << xp.second << '\n'; auto yit = yg.lower_bound({yp.first, -1}); if (yit != yg.end() && yit->first.second > yp.first.first) yit = yg.end(); auto xit = xg.lower_bound({xp.first, -1}); if (xit != xg.end() && xit->first.second > xp.first.first) xit = xg.end(); if (xit != xg.end()) { ix = xit->second; bool upyg = yit != yg.end(); auto yi = yii[xit->second]; auto tyit = yg.lower_bound({yi, -1}); auto npp = expand_ppp(*tyit, yp); yg.erase(tyit); yg.insert(npp); if (upyg) { yit = yg.lower_bound({yp.first, -1}); } yii[npp.second] = npp.first; } if (yit != yg.end()) { iy = yit->second; auto xi = xii[yit->second]; auto txit = xg.lower_bound({xi, -1}); auto npp = expand_ppp(*txit, xp); xg.erase(txit); xg.insert(npp); xii[npp.second] = npp.first; } if (ix != -1 && iy != -1) { ppp nppx = expand_ppp({xii[ix], ix}, {xii[iy], -1}); ppp nppy = expand_ppp({yii[ix], ix}, {yii[iy], -1}); xii.erase(iy); yii.erase(iy); auto tit = xg.find({xii[ix], ix}); xg.erase(tit); tit = xg.find({xii[iy], iy}); xg.erase(tit); tit = yg.find({yii[ix], ix}); yg.erase(tit); tit = yg.find({yii[iy], iy}); yg.erase(tit); xg.insert(nppx); yg.insert(nppy); xii[ix] = nppx.first; yii[iy] = nppy.first; } if (ix == -1 && iy == -1) { xg.insert(xp); yg.insert(yp); xii[xp.second] = xp.first; yii[yp.second] = yp.first; } } void solve() { int n; cin >> n; vector> e; for (int i = 0; i < n; i++) { ll a, b; cin >> a >> b; e.emplace_back(a, b); } for (int i = 0; i < n; i++) { auto p = e[i]; ppp xp = {{p.first, p.first}, i}; ppp yp = {{p.second, p.second}, i}; add_node(xp, yp); } cout << xg.size() - 1 << '\n'; } int main() { solve(); }