The tree chain splits

#include <bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e5 + 10;
int t[N << 2], lazy[N << 2], a[N], mod, root, n, m;
int d[N], siz[N], fa[N], son[N], top[N], id[N], rk[N], cnt;
vector<int> g[N];
 
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
 
void up(int k) { t[k] = add(t[l(k)], t[r(k)]); }
 
void update(int k, int l, int r, int x)
{
    lazy[k] = add(lazy[k], x);
    t[k] = add(t[k], mul(r - l + 1, x));
}
 
void down(int k, int l, int r)
{
    if(!lazy[k]) return;
    int m = l + r >> 1;
    update(l(k), l, m, lazy[k]);
    update(r(k), m + 1, r, lazy[k]);
    lazy[k] = 0;
}
 
void build(int k, int l, int r)
{
    if(l == r)
    {
        t[k] = rk[l];
        return;
    }
    int m = l + r >> 1;
    build(l(k), l, m);
    build(r(k), m + 1, r);
    up(k);
}
 
void change(int k, int l, int r, int L, int R, int x)
{
    if(L <= l && r <= R)
    {
        update(k, l, r, x);
        return;
    }
    down(k, l, r);
    int m = l + r >> 1;
    if(L <= m) change(l(k), l, m, L, R, x);
    if(R > m)  change(r(k), m + 1, r, L, R, x);
    up(k);
}
 
int query(int k, int l, int r, int L, int R)
{
    if(L <= l && r <= R) return t[k];
    down(k, l, r);
    int m = l + r >> 1, res = 0;
    if(L <= m) res = add(res, query(l(k), l, m, L, R));
    if(R > m) res = add(res, query(r(k), m + 1, r, L, R));
    return res;
}
 
void dfs1(int u, int father) // for the first time dfs Preprocessing , Deal with the depth , father , size 
{
    d[u] = d[father] + 1;
    fa[u] = father;
    siz[u] = 1;
    for(int v: g[u])
    {
        if(v == father) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
}
 
void dfs2(int u, int fa, int t) // The second time dfs Perform sectioning , Processing out dfs order , The top of each chain , as well as dfs Weight corresponding to order 
{
    top[u] = t;
    id[u] = ++cnt;
    rk[cnt] = a[u];
 
    if(siz[u] == 1) return;
    dfs2(son[u], u, t);
 
    for(int v: g[u])
    {
        if(v == fa || v == son[u]) continue;
        dfs2(v, u, v);
    }
}
 
void add(int u, int v, int x)
{
    while(top[u] != top[v]) // First consider the chain as a whole , When not in the same chain , Let the deeper point at the top of the chain jump up 
    {
        if(d[top[u]] < d[top[v]]) swap(u, v);
        change(1, 1, n, id[top[u]], id[u], x); // The jump process reprocesses the information of the points on the chain 
        u = fa[top[u]];
    }
    if(d[u] < d[v]) swap(u, v);                 // In the same chain , To continue processing 
    change(1, 1, n, id[v], id[u], x);           // From small to deep ,dfs Order from small to large 
}
 
int ask(int u, int v)
{
    int res = 0;
    while(top[u] != top[v])
    {
        if(d[top[u]] < d[top[v]]) swap(u, v);               // Attention is to compare top The depth of the , No u,v The depth of the 
        res = add(res, query(1, 1, n, id[top[u]], id[u]));
        u = fa[top[u]];
    }
    if(d[u] < d[v]) swap(u, v);
    res = add(res, query(1, 1, n, id[v], id[u]));         
    return res;
}
 
int main()
{
    scanf("%d%d%d%d", &n, &m, &root, &mod);
    _for(i, 1, n) scanf("%d", &a[i]);
    _for(i, 1, n - 1)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    dfs1(root, 0);
    dfs2(root, 0, root);
    build(1, 1, n);
 
    while(m--)
    {
        int op, x, y, z;
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d%d%d", &x, &y, &z);
            add(x, y, z);
        }
        else if(op == 2)
        {
            scanf("%d%d", &x, &y);
            printf("%d\n", ask(x, y));
        }
        else if(op == 3)
        {
            scanf("%d%d", &x, &z);
            change(1, 1, n, id[x], id[x] + siz[x] - 1, z);                 // use size Array push dfs The right end of the order 
        }
        else
        {
            scanf("%d", &x);
            printf("%d\n", query(1, 1, n, id[x], id[x] + siz[x] - 1));
        }
    }
 
    return 0;
}

Heuristic merge on tree

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 10;
int son[N], siz[N], c[N], cnt[N], mx, n;
vector<int> g[N];
ll sum, ans[N];
 
void dfs1(int u, int fa)
{
    siz[u] = 1;
    for(int v: g[u])
    {
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
}
 
void clear(int u, int fa)
{
    cnt[c[u]]--;
    for(int v: g[u])
    {
        if(v == fa) continue;
        clear(v, u);
    }
}
 
void add(int u)
{
    cnt[c[u]]++;
    if(cnt[c[u]] > mx)
    {
        mx = cnt[c[u]];
        sum = c[u];
    }
    else if(cnt[c[u]] == mx) sum += c[u];
}
 
void insert(int u, int fa)
{
    add(u);
    for(int v: g[u])
    {
        if(v == fa) continue;
        insert(v, u);
    }
}
 
void dfs2(int u, int fa)
{
    for(int v: g[u])
    {
        if(v == fa || v == son[u]) continue;
        dfs2(v, u);
        mx = sum = 0;
        clear(v, u);
    }
    if(son[u]) dfs2(son[u], u);
 
    for(int v: g[u])
    {
        if(v == fa || v == son[u]) continue;
        insert(v, u);
    }
    add(u);
 
    ans[u] = sum;
}
 
int main()
{
    scanf("%d", &n);
    _for(i, 1, n) scanf("%d", &c[i]);
    _for(i, 1, n - 1)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    dfs1(1, 0);
    dfs2(1, 0);
    _for(i, 1, n) printf("%lld ", ans[i]);
 
    return 0;
}

Linear base

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int M = 62;
ll d[M + 10];
bool zero;
 
void add(ll x)
{
    for(int i = M; i >= 0; i--)
        if(x & (1LL << i))              // Notice that it says 1LL Prevent explosion int
        {
            if(d[i]) x ^= d[i];
            else { d[i] = x; return; }   // Here is return No break
        }
    zero = true;                       // Be careful 0 A special sentence is required 
}
 
ll check(ll x)                         // Judge x Whether it can be represented by elements of linear basis   Similar to insertion 
{
    for(int i = M; i >= 0; i--)
        if(x & (1LL << i))
        {
            if(d[i]) x ^= d[i];
            else return false;
        }
    return true;
}
 
ll qmax()
{
    ll res = 0;
    for(int i = M; i >= 0; i--)        // Greedy from high to low   The essence is to try to make the high position as 1  Write simply like this 
        res = max(res, res ^ d[i]);
    return res;
}
 
ll qmin()                             // without 0 Words   The smallest d[i] That's the minimum 
{
    if(zero) return 0;
    _for(i, 0, M)
        if(d[i])
            return d[i];
}
 
ll kth(int k)                         // Query all XOR and middle k Small number 
{
    if(zero) k--;
    if(!k) return 0;
 
    _for(i, 0, M)                     // First deal with the linear basis   Note that the processed linear basis can still be used as usual 
        _for(j, 0, i - 1)
            if(d[i] & (1LL << j))
                d[i] ^= d[j];
 
    ll res = 0;
    _for(i, 0, M)
        if(d[i])
        {
            if(k & 1) res ^= d[i];
            k >>= 1;
        }
    return res;
}
 
int main()
{
    int n; scanf("%d", &n);
    _for(i, 1, n)
    {
        ll x; scanf("%lld", &x);
        add(x);
    }
    printf("%lld\n", qmax());
 
	return 0;
}

NTT

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 4e6 + 10, mod = 998244353, G = 3, Gi = 332748118; //NTT yes FFT The optimization of the , Faster , Avoid precision errors 
                                                                // meanwhile NTT You can take the mold , Module depends on the topic , Here we use 998244353 For example 
int n, m, limit = 1, l, r[N];                                   //N Open four times the data range 
ll a[N], b[N], c[N], ans[N];
 
ll binpow(ll a, ll b) 
{
    ll res = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}
 
void NTT(ll *A, int type)
{
    rep(i, 0, limit)
        if(i < r[i])
            swap(A[i], A[r[i]]);
 
    for(int mid = 1; mid < limit; mid <<= 1)
    {
        ll Wn = binpow(type == 1 ? G : Gi, (mod - 1) / (mid << 1));
        for(int j = 0; j < limit; j += (mid << 1))
        {
            ll w = 1;
            for(int k = 0; k < mid; k++, w = w * Wn % mod)
            {
                int x = A[j + k], y = w * A[j + k + mid] % mod;
                A[j + k] = (x + y) % mod;
                A[j + k + mid] = (x - y + mod) % mod;
            }
        }
    }
}
 
void read() // Read in n Degree polynomial sum m Sub polynomial 
{
    scanf("%d%d", &n, &m);
    _for(i, 0, n) scanf("%d", &a[i]), a[i] = (a[i] + mod) % mod;
    _for(i, 0, m) scanf("%d", &b[i]), b[i] = (b[i] + mod) % mod;
}
 
void solve()
{
    while(limit <= n + m) limit <<= 1, l++;
    rep(i, 0, limit) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    NTT(a, 1); NTT(b, 1);
    rep(i, 0, limit) c[i] = a[i] * b[i] % mod;
    NTT(c, -1);
    ll inv = binpow(limit, mod - 2);
    _for(i, 0, n + m) ans[i] = c[i] * inv % mod;
}
 
int main()
{
    read();
    solve();
    _for(i, 0, n + m) printf("%d ", ans[i]);
    return 0;
}

Linear inversion

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 5000 + 10;
const int mod = 1e9 + 7;
int inv[N];
 
int main()
{
    inv[0] = inv[1] = 1;
    _for(i, 2, 5000) inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
 
	return 0;
}

Take the right and check the collection

#include <cstdio>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e5 + 10;
int f[N], r[N], n, m;
 
int find(int x)
{
    if(f[x] == x) return x;
    int fa = f[x];
    f[x] = find(f[x]);
    r[x] = (r[x] + r[fa]) % 2;
    return f[x];
}
 
void Union(int x, int y)
{
    int fx = find(x), fy = find(y);
    if(fx == fy) return;
    f[fx] = fy;
    r[fx] = (r[x] + 1 + r[y]) % 2;
}
 
int main()
{
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        _for(i, 1, n) f[i] = i, r[i] = 0;
        while(m--)
        {
            char op[5]; int x, y;
            scanf("%s%d%d", op, &x, &y);
            if(op[0] == 'D') Union(x, y);
            else
            {
                if(find(x) != find(y)) puts("Not sure yet.");
                else
                {
                    if(r[x] == r[y]) puts("In the same gang.");
                    else puts("In different gangs.");
                }
            }
        }
    }
 
    return 0;
}

Line tree merge

#include <bits/stdc++.h>
#define num first
#define sum second
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
typedef long long ll;
const int N = 1e5 + 10;
int ls[N << 6], rs[N << 6], root[N], c[N], cnt, n;
pair<int, ll> t[N << 6];
vector<int> g[N];
ll ans[N];
 
void up(int k)
{
    if(t[ls[k]].num == t[rs[k]].num)
    {
        t[k] = make_pair(t[ls[k]].num, t[ls[k]].sum + t[rs[k]].sum);
        return;
    }
    t[k] = max(t[ls[k]], t[rs[k]]);
}
 
void add(int& k, int l, int r, int x)
{
    if(!k) k = ++cnt;
    if(l == r)
    {
        t[k].num = 1;
        t[k].sum = x;
        return;
    }
    int m = l + r >> 1;
    if(x <= m) add(ls[k], l, m, x);
    else add(rs[k], m + 1, r, x);
    up(k);
}
 
int merge(int x, int y, int l, int r)
{
    if(!x) return y;
    if(!y) return x;
    if(l == r)
    {
        t[x].num += t[y].num;
        t[x].sum = l;
        return x;
    }
    int m = l + r >> 1;
    ls[x] = merge(ls[x], ls[y], l, m);
    rs[x] = merge(rs[x], rs[y], m + 1, r);
    up(x);
    return x;
}
 
void dfs(int u, int fa)
{
    add(root[u], 1, n, c[u]);
    for(int v: g[u])
    {
        if(v == fa) continue;
        dfs(v, u);
        root[u] = merge(root[u], root[v], 1, n);
    }
    ans[u] = t[root[u]].sum;
}
 
int main()
{
    scanf("%d", &n);
    _for(i, 1, n) scanf("%d", &c[i]);
    _for(i, 1, n - 1)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    dfs(1, 0);
    _for(i, 1, n) printf("%lld ", ans[i]);
 
    return 0;
}

Dynamic open point line segment tree

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
int ls[N << 6], rs[N << 6], a[N], cnt, n, m, root;           // Be careful root Must be set to... At first 0
ll t1[N << 6], t2[N << 6];

void up(int k) 
{ 
	t1[k] = t1[ls[k]] + t1[rs[k]];
	t2[k] = t2[ls[k]] + t2[rs[k]];
}

void modify(int& k, int l, int r, int x, int p)
{
	if(!k) k = ++cnt;                                // Dynamic opening point 
	if(l == r)
	{
		t2[k] += p;
		t1[k] = t2[k] * x;
		return;
	}
	int m = l + r >> 1;
	if(x <= m) modify(ls[k], l, m, x, p);
	else modify(rs[k], m + 1, r, x, p);
	up(k);
}

ll query1(int k, int l, int r, int L, int R)
{
	if(!k) return 0;                                 // When asking, the empty node returns 0
	if(L <= l && r <= R) return t1[k];
	int m = l + r >> 1; ll res = 0;
	if(L <= m) res += query1(ls[k], l, m, L, R);
	if(R > m) res += query1(rs[k], m + 1, r, L, R);
	return res;
}

int query2(int k, int l, int r, int L, int R)
{
	if(!k) return 0;
	if(L <= l && r <= R) return t2[k];
	int m = l + r >> 1, res = 0;
	if(L <= m) res += query2(ls[k], l, m, L, R);
	if(R > m) res += query2(rs[k], m + 1, r, L, R);
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	modify(root, 0, 1e9, 0, n);  
	while(m--)
	{
		char op[5]; int x, y;
		scanf("%s%d%d", op, &x, &y);
		if(op[0] == 'U')
		{
			modify(root, 0, 1e9, a[x], -1); 
			modify(root, 0, 1e9, a[x] = y, 1);
		}
		else
		{
			int t = query2(root, 0, 1e9, y, 1e9);
			ll sum = query1(root, 0, 1e9, 0, y - 1); 
			if(sum >= 1LL * (x - t) * y) puts("TAK");
			else puts("NIE");
		}
	}

	return 0;
}

cdq Divide and conquer （ Three dimensional partial order problem ）

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int M = 2e5 + 10;
const int N = 1e5 + 10;
struct node
{
	int a, b, c, cnt, ans;
}t[N], s[N];
int f[M], k[N], m, n;
 
int lowbit(int x) { return x & -x; }
 
void add(int x, int p)
{
	for(; x <= m; x += lowbit(x))
		f[x] += p;
}
 
int sum(int x)
{
	int res = 0;
	for(; x; x -= lowbit(x))
		res += f[x];
	return res;
}
 
bool cmp1(node x, node y)
{
	if(x.a != y.a) return x.a < y.a;
	if(x.b != y.b) return x.b < y.b;
	return x.c < y.c;
}
 
bool cmp2(node x, node y)
{
	if(x.b != y.b) return x.b < y.b;
	return x.c < y.c;
}
 
void cdq(int l, int r)
{
	if(l == r) return;
	int mid = l + r >> 1;
	cdq(l, mid); cdq(mid + 1, r);
 
	sort(s + l, s + mid + 1, cmp2);
	sort(s + mid + 1, s + r + 1, cmp2);
	int i = l, j = mid + 1;
	for(; j <= r; j++)
	{
		while(s[i].b <= s[j].b && i <= mid)
		{
			add(s[i].c, s[i].cnt);
			i++;
		}
		s[j].ans += sum(s[j].c);
	}
	_for(t, l, i - 1) add(s[t].c, -s[t].cnt);                     // Note that emptying here is not the entire left section , The left interval may not be traversed 
}
 
int main()
{
	scanf("%d%d", &n, &m);
	_for(i, 1, n) scanf("%d%d%d", &t[i].a, &t[i].b, &t[i].c);
	sort(t + 1, t + n + 1, cmp1);
 
	int same = 0, p = 0;
	_for(i, 1, n)
	{
		same++;
		if(t[i].a != t[i + 1].a || t[i].b != t[i + 1].b || t[i].c != t[i + 1].c)
		{
			s[++p] = t[i];
			s[p].cnt = same;
			same = 0;
		}
	}
 
	cdq(1, p);
	_for(i, 1, p) k[s[i].ans + s[i].cnt - 1] += s[i].cnt;
	_for(i, 0, n - 1) printf("%d\n", k[i]);
 
	return 0; 
}

Gauss elimination （ Solve a system of linear equations ）

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 15;
double a[N][N], p[N][N];
int n;
 
void build()
{
    scanf("%d", &n);
	_for(i, 1, n + 1)
		_for(j, 1, n)
			scanf("%lf", &p[i][j]);
	_for(i, 1, n)
		_for(k, 1, n) 
		{
			double x1 = p[i][k], x2 = p[i + 1][k];
			a[i][k] = 2 * (x2 - x1);
			a[i][n + 1] += x2 * x2 - x1 * x1;
		}
}
 
void Gauss()
{
	_for(j, 1, n)
	{
		int p = j;                           
		while(!a[p][j] && p <= n) p++;
		swap(a[p], a[j]);                   
		_for(i, 1, n)                         
			if(i != j)
			{
				double t = a[i][j] / a[j][j];
				_for(k, 1, n + 1) a[i][k] -= t * a[j][k];
			}
	}
	_for(i, 1, n) printf("%.3f ", a[i][n + 1] / a[i][i]);
}
 
int main()
{
    build();
	Gauss();
	return 0; 
}

The suffix array

/*
    sa[i]  Ranked as i The position of the suffix 
    height lcp(sa[i], sa[i - 1])  The ranking is i The suffix and rank of i−1 The longest common prefix of the suffix 
    H[i]：height[rak[i]], namely i The longest common prefix between the suffix number and the suffix before it 
 
     The longest public substring （ Can overlap ） height Array maximum   Because the ranking of the two substrings of the longest common prefix must be adjacent 
     Essentially different number of strings   Enumerate each suffix i  The contribution to the answer is  len − sa[i] + 1 − height[i]
     The largest common prefix of two suffixes   Make x=rank[i],y=rank[j],x < y, that lcp(i,j)=min(height[x+1],height[x+2]…height[y]).lcp(i,i)=n-sa[i].  use ST Table or segment tree 
*/
 
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
 
const int N = 1e6 + 10;
int x[N], y[N], c[N], sa[N], rk[N], height[N], wt[30];
int n, m;
char s[N];
 
void get_SA()
{
    _for(i, 1, n) ++c[x[i] = s[i]];
    _for(i, 2, m) c[i] += c[i - 1];
    for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
    for(int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        _for(i, n - k + 1, n) y[++num] = i;
        _for(i, 1, n) if(sa[i] > k) y[++num] = sa[i] - k;
        _for(i, 1, m) c[i] = 0;
        _for(i, 1, n) ++c[x[i]];
        _for(i, 2, m) c[i] += c[i - 1];
        for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1; num = 1;
        _for(i, 2, n) 
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        if(num == n) break;
        m = num;
    }
}
 
void get_height()
{
    int k = 0;
    _for(i, 1, n) rk[sa[i]] = i;
    _for(i, 1, n)
    {
        if(rk[i] == 1) continue;
        if(k) k--;
        int j = sa[rk[i] - 1];
        while(j + k <= n && i + k <= n && s[i + k] == s[j + k]) k++;
        height[rk[i]] = k;
    }
}
 
int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    m = 122;                //m Represents the number of characters  ascll('z')=122 
                            // The range of the barrel is 1~m
    get_SA();
    _for(i, 1, n) printf("%d ", sa[i]);
    return 0;
}

convex hull

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;
 
const double eps = 1e-8;
const int N = 1e5 + 10;
 
struct point
{
	double x, y;
	point(double x = 0, double y = 0) : x(x), y(y) {}
}st[N], p[N];
int n, top;
 
point operator - (point a, point b) { return {a.x - b.x, a.y - b.y}; }
double operator ^ (point a, point b) { return a.x * b.y - a.y * b.x; } // Cross product mathematically returns a vector , The program returns the value here  
double dis(point a, point b) { return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); }
 
bool cmp(point a, point b) // Abscissa first keyword , Ordinate second keyword  
{
	if(fabs(a.x - b.x) < eps) 
		return a.y < b.y;
	return a.x < b.x;
}
 
int main()
{
	scanf("%d", &n);
	_for(i, 1, n) scanf("%lf%lf", &p[i].x, &p[i].y);
	sort(p + 1, p + n + 1, cmp);
	
	st[++top] = p[1]; // First add the first point , The first point must be the point on the convex hull  
	_for(i, 2, n)  // Find the lower semi convex hull  
	{
		while(top >= 2 && ((st[top] - st[top - 1]) ^ (p[i] - st[top - 1])) < 0) top--; // Here is a case of multiple points on one side , That is, the equal case  
		st[++top] = p[i];                                                              // But this question does not affect the result  
	}                                                                                  // If you want to remove it, change it to <=0  And write eps 
	for(int i = n - 1; i >= 1; i--) // Find the upper semi convex hull , Direct copy , Just change the cycle order  
	{
		while(top >= 2 && ((st[top] - st[top - 1]) ^ (p[i] - st[top - 1])) < 0) top--; 
		st[++top] = p[i];
	}
	
	double ans = 0;
	_for(i, 1, top - 1) // At last, the beginning and end of the stack are starting points , So we can find the distance directly  
		ans += dis(st[i], st[i + 1]);
	printf("%.2lf\n", ans);
	
	return 0;
}