Pastein: шаблон по геометрии: struct vec { int x, y; long long len2() { return 1ll * x * x + 1ll * y * y; } long double len() { return sqrt(len2());

Загрузка данных
шаблон по геометрии: struct vec {
    int x, y;

    long long len2() {
        return 1ll * x * x + 1ll * y * y;
    }

    long double len() {
        return sqrt(len2());
    }
};

ostream &operator<<(ostream &os, const vec &a) {
    return os << a.x << " " << a.y;
}

istream &operator>>(istream &in, vec &a) {
    return in >> a.x >> a.y;
}

vec operator+(const vec &a, const vec &b) {
    return {a.x + b.x, a.y + b.y};
}

vec operator-(const vec &a, const vec &b) {
    return {a.x - b.x, a.y - b.y};
}

vec operator*(const vec &a, const int &k) {
    return {a.x * k, a.y * k};
}

vec operator*(const int &k, const vec &a) {
    return {a.x * k, a.y * k};
}

long long operator*(const vec &a, const vec &b) {
    return 1ll * a.x * b.x + 1ll * a.y * b.y;
}

long long operator%(const vec &a, const vec &b) {
    return 1ll * a.x * b.y - 1ll * a.y * b.x;
}             
                                                          проверить находится ли точка в многоугольнике:                   bool Func(pii x, vpii &v) {
    int n = v.size();
    if (vec(v[1] - v[0], x - v[0]) < 0) {
        return false;
    }
    if (vec(v[n - 1] - v[0], x - v[0]) > 0) {
        return false;
    }
    int l = 1, r = n - 1;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (vec(v[mid] - v[0], x - v[0]) >= 0) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return vec(v[l + 1] - v[l], x - v[l]) > 0;
}           
                                                       выпуклая оболочка и ее площадь: 
struct Node {
    ll a, b;
};

ll vec(Node a, Node b) {
    return a.a * b.b - a.b * b.a;
}

Node operator-(Node a, Node b) {
    return {a.a - b.a, a.b - b.b};
}

bool cmp(Node &a, Node &b) {
    if (a.a == b.a) {
        return a.b < b.b;
    }
    return a.a < b.a;
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector<Node> v;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.emplace_back(a, b);
    }
    sort(v.begin(), v.end(), cmp);
    vint p;
    p.push_back(0);
    for (int i = 1; i < n; i++) {
        while (p.size() >= 2 && vec(v[i] - v[p[p.size() - 2]], v[p.back()] - v[p[p.size() - 2]]) >= 0) {
            p.pop_back();
        }
        p.push_back(i);
    }
    unsigned int t = p.size();
    for (int i = n - 2; i >= 0; i--) {
        while (p.size() > t && vec(v[i] - v[p[p.size() - 2]], v[p.back()] - v[p[p.size() - 2]]) >= 0) {
            p.pop_back();
        }
        p.push_back(i);
    }
    p.pop_back();
    ll ans = 0;
    n = p.size();
    cout << n << '\n';
    for (int i = 0; i < n; i++) {
        ans += vec(v[p[i]], v[p[(i + 1) % n]]);
    }
    for (int x : p) {
        cout << v[x].a << ' ' << v[x].b << '\n';
    }
    cout << fixed << setprecision(10) << abs((ld) ans / 2.0);
}

точки сочленения:                                                    int k = 0;
vector<bool> used, ans;
vector<int> up, d;
vector<vector<int>> g;
 
 
void dfs(int u, int p) {
    int children = 0;
    used[u] = true;
    up[u] = d[u] = (p == -1 ? 0 : d[p] + 1);
    for (const int v : g[u]) {
        if (v == p) {
            continue;
        }
        if (used[v]) {
            up[u] = min(up[u], d[v]);
        } else {
            dfs(v, u);
            children++;
            up[u] = min(up[u], up[v]);
            if (d[u] <= up[v] && p != -1) {
                if (!ans[u]) {
                    k++;
                }
                ans[u] = true;
            }
        }
        if (p == -1 && children > 1) {
            if (!ans[u]) {
                k++;
            }
            ans[u] = true;
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, u, v;
    cin >> n >> m;
    used.assign(n, false);
    ans.assign(n, false);
    g.resize(n);
    up.resize(n);
    d.resize(n);
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }
    cout << k << '\n';
    for (int i = 0; i < n; i++) {
        if (ans[i]) {
            cout << i + 1 << "\n";
        }
    }
}      
                                                              мосты:
 int k = 0;
vector<bool> used;
vector<int> up, d;
vector<pair<int, int>> ans;
vector<vector<int>> g;
map<pair<int, int>, int> mp;
 
 
void dfs(int u, int p) {
    used[u] = true;
    up[u] = d[u] = (p == -1 ? 0 : d[p] + 1);
    for (int v : g[u]) {
        if (v == p) {
            continue;
        }
        if (used[v]) {
            up[u] = min(up[u], d[v]);
        } else {
            dfs(v, u);
            up[u] = min(up[u], up[v]);
            if (d[u] < up[v]) {
                ans.push_back({min(u, v), max(u, v)});
            }
        }
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, u, v;
    cin >> n >> m;
    used.assign(n, false);
    g.resize(n);
    up.resize(n);
    d.resize(n);
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
        mp[{min(u, v), max(u, v)}] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }
    vector<int> a;
    n = ans.size();
    for (int i = 0; i < n; i++) {
        a.push_back(mp[ans[i]]);
    }
    sort(a.begin(), a.end());
    n = a.size();
    cout << n << '\n';
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
} 
                                                          пересечение прямых: 
 vec A, B, C, D;
    cin >> A >> B >> C >> D;
    vec AB = B - A;
    vec CD = D - C;
    vec AC = C - A;
    if (AB % CD == 0) {
        if (AC % CD == 0) {
            cout << 2;
            return 0;
        }
        cout << 0;
        return 0;
    }
    cout << 1 << " ";
    ld t = (ld) (AC % CD) / (AB % CD);
    cout << A + (AB ^ t); 


неявный ДД:                                                       struct Node {
    int prior, val, sz;
    Node *l = nullptr, *r = nullptr;
    explicit Node(const int _key) { prior = rand(), val = _key, sz = 1; }
};

Node *root = nullptr;

using Pair = pair<Node *, Node *>;

int get_sz(Node *x) {
    if (x == nullptr) {
        return 0;
    }
    return x->sz;
}

void upd(Node *v) {
    if (v) {
        v->sz = get_sz(v->l) + get_sz(v->r) + 1;
    }
}

Node *merge(Node *l, Node *r) {
    if (!l) {
        return r;
    }
    if (!r) {
        return l;
    }
    if (l->prior > r->prior) {
        l->r = merge(l->r, r);
        upd(l);
        return l;
    }
    r->l = merge(l, r->l);
    upd(r);
    return r;
}

Pair split(Node *p, int k) {
    if (!p) {
        return {nullptr, nullptr};
    }
    int x = get_sz(p->l) + 1;
    if (x <= k) {
        Pair q = split(p->r, k - x);
        p->r = q.first;
        upd(p);
        return {p, q.second};
    }
    Pair q = split(p->l, k);
    p->l = q.second;
    upd(p);
    return {q.first, p};
}


касательные к окружности из точки: // Дано: x0, y0, R (окружность) и x1, y1 (точка вне окружности)

// 1. Дистанция и углы
double d     = sqrt(pow(x1 - x0, 2) + pow(y1 - y0, 2));
double alpha = atan2(y1 - y0, x1 - x0);
double phi   = acos(R / d);

// 2. Координаты первой точки касания
double xt1 = x0 + R * cos(alpha + phi);
double yt1 = y0 + R * sin(alpha + phi);

// 3. Координаты второй точки касания
double xt2 = x0 + R * cos(alpha - phi);
double yt2 = y0 + R * sin(alpha - phi);  


хеши, задача сравнение подстрок:                                const int P = 101;
const int MOD = 1000000007;
vector<int> sp, h;

int get_hash(int r, int l) {
    return ((h[r] - 1ll * (1ll * h[l] * sp[r - l]) % MOD) + MOD) % MOD;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    string s;
    cin >> s;
    int n = s.length();
    h.resize(n + 1);
    sp.resize(n + 1);
    sp[0] = 1;
    h[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = (1ll * h[i - 1] * P % MOD + s[i - 1]) % MOD;
        sp[i] = (1ll * sp[i - 1] * P) % MOD;
    }
    int k, l1, r1, l2, r2;
    cin >> k;
    while (k--) {
        cin >> l1 >> r1 >> l2 >> r2;
        l1--;
        l2--;
        int m = min(r1 - l1, r2 - l2);
        int l = 0, r = m;
        while (l + 1 != r) {
            int mid = (l + r) / 2;
            const int A = get_hash(mid + l1, l1);
            const int B = get_hash(mid + l2, l2);
            if (A == B) {
                l = mid;
            } else {
                r = mid;
            }
        }
        int ans = r;
        const int A = get_hash(ans + l1, l1);
        const int B = get_hash(ans + l2, l2);
        if (A != B) {
            ans = l;
        }
        if (ans == m) {
            if (r1 - l1 > r2 - l2) {
                cout << "No\n";
            } else if (r1 - l1 < r2 - l2) {
                cout << "No\n";
            } else {
                cout << "Yes\n";
            }
        } else {
            cout << "No\n";
        }
    }
}        


максимальное независимое множество, все остальные вершины - минимальное вершиное покрытие:  
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> g;
vector<int> match_r, match_l;
vector<bool> used, visited_l, visited_r;

// Алгоритм Куна для поиска паросочетания
bool dfs_kuhn(int v) {
    if (used[v]) return false;
    used[v] = true;
    for (int to : g[v]) {
        if (match_r[to] == -1 || dfs_kuhn(match_r[to])) {
            match_r[to] = v;
            match_l[v] = to;
            return true;
        }
    }
    return false;
}

// Обход для поиска МВП/МНМ
void dfs_mis(int v) {
    visited_l[v] = true;
    for (int to : g[v]) {
        // Идем по ребру не из паросочетания (L -> R)
        if (match_l[v] != to && !visited_r[to]) {
            visited_r[to] = true;
            // Идем по ребру из паросочетания (R -> L)
            if (match_r[to] != -1) dfs_mis(match_r[to]);
        }
    }
}

int main() {
    int n, m, k; // n - левая доля, m - правая, k - ребра
    cin >> n >> m >> k;
    g.resize(n);
    match_r.assign(m, -1);
    match_l.assign(n, -1);

    for (int i = 0; i < k; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
    }

    // 1. Максимальное паросочетание
    for (int i = 0; i < n; ++i) {
        used.assign(n, false);
        dfs_kuhn(i);
    }

    // 2. Поиск МНМ
    visited_l.assign(n, false);
    visited_r.assign(m, false);
    for (int i = 0; i < n; ++i) {
        if (match_l[i] == -1) dfs_mis(i);
    }

    cout << "Вершины МНМ в левой доле: ";
    for (int i = 0; i < n; i++) if (visited_l[i]) cout << i << " ";
    cout << "\nВершины МНМ в правой доле: ";
    for (int i = 0; i < m; i++) if (!visited_r[i]) cout << i << " ";

    return 0;
}

LCA -   сумма чисел в вершинах на пути: 

vector<vint> gr;
vint d, p;

void dfs(ll v) {
    for (ll u : gr[v]) {
        if (u == p[v]) {
            continue;
        }
        d[u] = d[v] + 1;
        p[u] = v;
        dfs(u);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    gr.assign(n, {});
    d.assign(n, 0);
    p.assign(n, 0);
    vint v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }

    dfs(0);
    int l = log2(n) + 1;
    vector<vpii> dp(n, vpii(l, {0, 0}));
    for (int i = 1; i < n; i++) {
        dp[i][0].first = p[i];
        dp[i][0].second = v[p[i]];
    }
    for (int i = 1; i < l; i++) {
        for (int j = 0; j < n; j++) {
            dp[j][i] = dp[dp[j][i - 1].first][i - 1];
            dp[j][i].second += dp[j][i - 1].second;
        }
    }
    int m;
    cin >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if (x == y) {
            cout << v[x] << '\n';
            continue;
        }
        if (d[x] > d[y]) {
            swap(x, y);
        }
        ll sum = v[y];
        for (int i = l - 1; i >= 0; i--) {
            if (d[dp[y][i].first] >= d[x]) {
                sum += dp[y][i].second;
                y = dp[y][i].first;
            }
        }
        if (x == y) {
            cout << sum << '\n';
            continue;
        }
        sum += v[x];
        for (int i = l - 1; i >= 0; i--) {
            if (dp[x][i].first != dp[y][i].first) {
                sum += dp[y][i].second + dp[x][i].second;
                x = dp[x][i].first;
                y = dp[y][i].first;
            }
        }
        sum += v[p[x]];
        cout << sum << '\n';
    }
}


задача RMQ корняха:
int n;
    cin >> n;
    vint v(n);
    int m = n / K + 1;
    vint ans(m, INF);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        ans[i / K] = min(ans[i / K], v[i]);
    }
    string s;
    while (cin >> s) {
        if (s[0] == 's') {
            int i, x;
            cin >> i >> x;
            i--;
            v[i] = x;
            int l = (i / K) * K, r = l + K;
            ans[i / K] = INF;
            for (int j = l; j < r && j < n; j++) {
                ans[i / K] = min(ans[i / K], v[j]);
            }
            continue;
        }
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        int aw = INF;
        for (int i = l; i <= r; i++) {
            if (i % K == 0 && i + K - 1 <= r) {
                aw = min(aw, ans[i / K]);
                i += K - 1;
            } else {
                aw = min(aw, v[i]);
            }
        }
        cout << aw << '\n';
    }


МО, сначала расширяем потом сужаем:

struct Node {
    int l, r, i;
};
 
bool cmp(const Node &a, const Node &b) {
    int x = a.l / K, y = b.l / K;
    if (x != y) {
        return x < y;
    }
    if (x & 1) {
        return a.r < b.r;
    }
    return a.r > b.r;
}
Больше возможностей при регистрации:
