#include using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef vector vi; typedef vector vl; typedef long double ld; typedef unsigned long long ull; typedef pair pii; int n; const int MAXN = 200000; const int MAXX = 1000000000; // Delauney triangulation from cp-algorithms bool ge(const ll& a, const ll& b) { return a >= b; } bool le(const ll& a, const ll& b) { return a <= b; } bool eq(const ll& a, const ll& b) { return a == b; } bool gt(const ll& a, const ll& b) { return a > b; } bool lt(const ll& a, const ll& b) { return a < b; } int sgn(const ll& a) { return a >= 0 ? a ? 1 : 0 : -1; } struct pt { ll x, y; pt() { } pt(ll _x, ll _y) : x(_x), y(_y) { } pt operator-(const pt& p) const { return pt(x - p.x, y - p.y); } ll cross(const pt& p) const { return x * p.y - y * p.x; } ll cross(const pt& a, const pt& b) const { return (a - *this).cross(b - *this); } ll dot(const pt& p) const { return x * p.x + y * p.y; } ll dot(const pt& a, const pt& b) const { return (a - *this).dot(b - *this); } ll sqrLength() const { return this->dot(*this); } bool operator==(const pt& p) const { return eq(x, p.x) && eq(y, p.y); } }; const pt inf_pt = pt(1e18, 1e18); struct QuadEdge { pt origin; QuadEdge* rot = nullptr; QuadEdge* onext = nullptr; bool used = false; QuadEdge* rev() const { return rot->rot; } QuadEdge* lnext() const { return rot->rev()->onext->rot; } QuadEdge* oprev() const { return rot->onext->rot; } pt dest() const { return rev()->origin; } }; QuadEdge* make_edge(pt from, pt to) { QuadEdge* e1 = new QuadEdge; QuadEdge* e2 = new QuadEdge; QuadEdge* e3 = new QuadEdge; QuadEdge* e4 = new QuadEdge; e1->origin = from; e2->origin = to; e3->origin = e4->origin = inf_pt; e1->rot = e3; e2->rot = e4; e3->rot = e2; e4->rot = e1; e1->onext = e1; e2->onext = e2; e3->onext = e4; e4->onext = e3; return e1; } void splice(QuadEdge* a, QuadEdge* b) { swap(a->onext->rot->onext, b->onext->rot->onext); swap(a->onext, b->onext); } void delete_edge(QuadEdge* e) { splice(e, e->oprev()); splice(e->rev(), e->rev()->oprev()); delete e->rev()->rot; delete e->rev(); delete e->rot; delete e; } QuadEdge* connect(QuadEdge* a, QuadEdge* b) { QuadEdge* e = make_edge(a->dest(), b->origin); splice(e, a->lnext()); splice(e->rev(), b); return e; } bool left_of(pt p, QuadEdge* e) { return gt(p.cross(e->origin, e->dest()), 0); } bool right_of(pt p, QuadEdge* e) { return lt(p.cross(e->origin, e->dest()), 0); } template T det3(T a1, T a2, T a3, T b1, T b2, T b3, T c1, T c2, T c3) { return a1 * (b2 * c3 - c2 * b3) - a2 * (b1 * c3 - c1 * b3) + a3 * (b1 * c2 - c1 * b2); } bool in_circle(pt a, pt b, pt c, pt d) { // If there is __int128, calculate directly. // Otherwise, calculate angles. #if defined(__LP64__) || defined(_WIN64) __int128 det = -det3<__int128>(b.x, b.y, b.sqrLength(), c.x, c.y, c.sqrLength(), d.x, d.y, d.sqrLength()); det += det3<__int128>(a.x, a.y, a.sqrLength(), c.x, c.y, c.sqrLength(), d.x, d.y, d.sqrLength()); det -= det3<__int128>(a.x, a.y, a.sqrLength(), b.x, b.y, b.sqrLength(), d.x, d.y, d.sqrLength()); det += det3<__int128>(a.x, a.y, a.sqrLength(), b.x, b.y, b.sqrLength(), c.x, c.y, c.sqrLength()); return det > 0; #else auto ang = [](pt l, pt mid, pt r) { ll x = mid.dot(l, r); ll y = mid.cross(l, r); long double res = atan2((long double)x, (long double)y); return res; }; long double kek = ang(a, b, c) + ang(c, d, a) - ang(b, c, d) - ang(d, a, b); if (kek > 1e-8) return true; else return false; #endif } pair build_tr(int l, int r, vector& p) { if (r - l + 1 == 2) { QuadEdge* res = make_edge(p[l], p[r]); return make_pair(res, res->rev()); } if (r - l + 1 == 3) { QuadEdge *a = make_edge(p[l], p[l + 1]), *b = make_edge(p[l + 1], p[r]); splice(a->rev(), b); int sg = sgn(p[l].cross(p[l + 1], p[r])); if (sg == 0) return make_pair(a, b->rev()); QuadEdge* c = connect(b, a); if (sg == 1) return make_pair(a, b->rev()); else return make_pair(c->rev(), c); } int mid = (l + r) / 2; QuadEdge *ldo, *ldi, *rdo, *rdi; tie(ldo, ldi) = build_tr(l, mid, p); tie(rdi, rdo) = build_tr(mid + 1, r, p); while (true) { if (left_of(rdi->origin, ldi)) { ldi = ldi->lnext(); continue; } if (right_of(ldi->origin, rdi)) { rdi = rdi->rev()->onext; continue; } break; } QuadEdge* basel = connect(rdi->rev(), ldi); auto valid = [&basel](QuadEdge* e) { return right_of(e->dest(), basel); }; if (ldi->origin == ldo->origin) ldo = basel->rev(); if (rdi->origin == rdo->origin) rdo = basel; while (true) { QuadEdge* lcand = basel->rev()->onext; if (valid(lcand)) { while (in_circle(basel->dest(), basel->origin, lcand->dest(), lcand->onext->dest())) { QuadEdge* t = lcand->onext; delete_edge(lcand); lcand = t; } } QuadEdge* rcand = basel->oprev(); if (valid(rcand)) { while (in_circle(basel->dest(), basel->origin, rcand->dest(), rcand->oprev()->dest())) { QuadEdge* t = rcand->oprev(); delete_edge(rcand); rcand = t; } } if (!valid(lcand) && !valid(rcand)) break; if (!valid(lcand) || (valid(rcand) && in_circle(lcand->dest(), lcand->origin, rcand->origin, rcand->dest()))) basel = connect(rcand, basel->rev()); else basel = connect(basel->rev(), lcand->rev()); } return make_pair(ldo, rdo); } vector> delaunay(vector p) { sort(p.begin(), p.end(), [](const pt& a, const pt& b) { return lt(a.x, b.x) || (eq(a.x, b.x) && lt(a.y, b.y)); }); auto res = build_tr(0, (int)p.size() - 1, p); QuadEdge* e = res.first; vector edges = {e}; while (lt(e->onext->dest().cross(e->dest(), e->origin), 0)) e = e->onext; auto add = [&p, &e, &edges]() { QuadEdge* curr = e; do { curr->used = true; p.push_back(curr->origin); edges.push_back(curr->rev()); curr = curr->lnext(); } while (curr != e); }; add(); p.clear(); int kek = 0; while (kek < (int)edges.size()) { if (!(e = edges[kek++])->used) add(); } vector> ans; for (int i = 0; i < (int)p.size(); i += 3) { ans.push_back(make_tuple(p[i], p[i + 1], p[i + 2])); } return ans; } // // Union find from KACTL struct UF { vi e; UF(int n) : e(n, -1) {} bool sameSet(int a, int b) { return find(a) == find(b); } int size(int x) { return -e[find(x)]; } int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); } bool join(int a, int b) { a = find(a), b = find(b); if (a == b) return false; if (e[a] > e[b]) swap(a, b); e[a] += e[b]; e[b] = a; return true; } }; ll ph(pt p){ return p.x*2*MAXX+p.y; } double emst(vector pts){ vector> triangles = delaunay(pts); vector W; vi U,V; map to_ind; int i = 0; trav(p, pts){ to_ind[ph(p)] = i; i++; } set S; trav(v, triangles){ vi I = {to_ind[ph(get<0>(v))], to_ind[ph(get<1>(v))], to_ind[ph(get<2>(v))]}; rep(c1,0,3){ int i = I[c1]; int j = I[(c1+1)%3]; if(i > j)swap(i, j); if(S.find({i,j}) == S.end()){ pt d = pts[i]-pts[j]; ll w = d.sqrLength(); W.push_back(w); U.push_back(i); V.push_back(j); S.insert({i, j}); } } } // Delaunay doesn't work when all points are on a line... vector > line; rep(c1,0,sz(pts)){ line.push_back({ph(pts[c1]), c1}); } sort(all(line)); rep(c1,1,sz(line)){ int i = line[c1-1].second; int j = line[c1].second; if(i > j)swap(i, j); if(S.find({i,j}) == S.end()){ pt d = pts[i]-pts[j]; ll w = d.sqrLength(); W.push_back(w); U.push_back(i); V.push_back(j); S.insert({i, j}); } } vector > edges; rep(c1,0,sz(W)){ edges.push_back({W[c1], c1}); } set edge_set; sort(all(edges)); UF uf(sz(pts)); vi deg(sz(pts), 0); double ans = 0.0; trav(p, edges){ int e = p.second; if(!uf.sameSet(U[e], V[e])){ uf.join(U[e], V[e]); ans += sqrt(p.first); } } return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; vector pts; rep(c1,0,n){ ll x,y; cin >> x >> y; pt p(x, y); pts.push_back({x, y}); } double ans = emst(pts); cout << setprecision(18) << ans << "\n"; return 0; }