cp-reference-codes/src/6-geometry/geom_bulldozer.cpp at main · manoflearning/cp-reference-codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include "geom_base.cpp"

// what: enumerate point orderings under rotating direction for angle-sweep counting.
// time: O(n^2 log n); memory: O(n^2)
// constraint: orders correspond to direction angle in [0, pi); points processed in-place.
// usage: bulldozer(p, [&](const vector<pt> &cur) { /* use order */ });
struct bd_line {
    int u, v;
    ll dx, dy; // dx >= 0
    bool operator<(const bd_line &rhs) const {
        if (dy * rhs.dx != rhs.dy * dx) return dy * rhs.dx < rhs.dy * dx;
        return tie(u, v) < tie(rhs.u, rhs.v);
    }
    bool operator==(const bd_line &rhs) const {
        return dy * rhs.dx == rhs.dy * dx;
    }
};

template <class F>
void bulldozer(vector<pt> &p, F f) {
    // goal: visit each distinct angular order once.
    int n = sz(p);
    sort(all(p));
    vector<pt> base = p;
    vector<int> pos(n);
    iota(all(pos), 0);
    vector<bd_line> ln;
    ln.reserve(1LL * n * (n - 1) / 2);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int u = i, v = j;
            ll dx = p[v].x - p[u].x;
            ll dy = p[v].y - p[u].y;
            if (dx < 0 || (dx == 0 && dy < 0)) {
                dx = -dx, dy = -dy;
                swap(u, v);
            }
            ln.push_back({u, v, dx, dy});
        }
    }
    sort(all(ln));
    f(p);
    for (int i = 0, j = 0; i < sz(ln); i = j) {
        while (j < sz(ln) && ln[j] == ln[i]) j++;
        ll dx = ln[i].dx, dy = ln[i].dy;
        if (dx == 0) break;
        unordered_map<ll, vector<int>> mp;
        mp.reserve((j - i) * 2 + 1);
        for (int k = i; k < j; k++) {
            int u = ln[k].u, v = ln[k].v;
            ll c = -dy * base[u].x + dx * base[u].y;
            mp[c].push_back(u);
            mp[c].push_back(v);
        }
        for (auto &it : mp) {
            auto &vec = it.sc;
            sort(all(vec));
            vec.erase(unique(all(vec)), vec.end());
            sort(all(vec), [&](int a, int b) { return pos[a] < pos[b]; });
            for (int l = 0, r = sz(vec) - 1; l < r; l++, r--) {
                int u = vec[l], v = vec[r];
                int pu = pos[u], pv = pos[v];
                if (pu == pv) continue;
                swap(p[pu], p[pv]);
                swap(pos[u], pos[v]);
            }
        }
        f(p);
    }
}

void bulldozer(vector<pt> &p) {
    bulldozer(p, [](const vector<pt> &) {});
}