这部分内容重点是扫描线算法

简单几何问题

重点理解一下小数二分

UVA1421
UVA1421

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
const double eps = 1e-6;
const int maxn = 1e4 + 10;
int n;
double maxx = 0;

class A {
public:
    double l, r, h;
    bool operator< (const A &rhs) const {
        return h < rhs.h;
    }
} a[maxn];

// -1 , decrease
// 1, increase
int check(double x) {
    double R = atan2(a[0].h, a[0].r - (double )x);
    double L = atan2(a[0].h, a[0].l - (double )x);

    _for(i, 1, n) {
        double r = atan2(a[i].h, a[i].r - (double )x);
        double l = atan2(a[i].h, a[i].l - (double )x);

        if (l < R - eps) return -1;
        if (r > L + eps) return 1;

        chmax(R, r);
        chmin(L, l);
    }
    return 0;
}

bool solve() {
    sort(a, a+n);

    int le = 0, ri = maxx;
    //debug(ri);
    while (ri - le > eps) {
        double mid = (le + ri) / 2;
        if (check(mid) == 0) return true;
        if (check(mid) == -1) ri = mid;
        else if (check(mid) == 1) le = mid + 1;
    }
    return false;
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;

    while (kase--) {
        init();
        scanf("%lf%d", &maxx, &n);
        _for(i, 0, n) {
            scanf("%lf%lf%lf", &a[i].h, &a[i].l, &a[i].r);
            chmax(maxx, a[i].r);
        }

        // then solve
        if (solve()) printf("YES\n");
        else printf("NO\n");
    }
}

图形排列

HDU4092
HDU4092
HDU4092
HDU4092

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(Pizz u) {
    if (u.cnt == maxn + 1) return;
    if (search(u)) return;

    printf("Depth: %d\n", u.cnt);
    insToSet(u);
    ans[u.cnt]++;

    _for(i, 0, u.cnt) {
        _for(dir, 0, 3) {
            Trian t = u.arr[i].add(dir);
            if (u.add(t)) {
                dfs(u);
                u.remove();
            }
        }
    }
}

整数问题的枚举

UVA10825
UVA10825

特别注意，用数组来模拟 nn 位数的乘法，进位的问题

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
75
76
77
78
79
80
81
82
const int maxn = 10;
int vis[maxn];

vector<int> buf, ans, a;
int n, m, p;
bool ok = false;

void prework() {
    buf.clear();
    _rep(i, 1, m) buf.push_back((p*i) % n);
    sort(buf.begin(), buf.end());
}

bool check(const vector<int> &ans) {
    vector<int> s = ans;
    sort(s.begin(), s.end());
    _rep(i, 2, m) {
        vector<int> t = ans;
        for (auto &u : t) u *= i;
        for (int j = 0; j < t.size(); j++) {
            if (j != t.size() - 1) {
                t[j+1] += t[j] / n;
                t[j] %= n;
            }
        }
        sort(t.begin(), t.end());
        _for(j, 0, t.size()) if (t[j] != s[j]) return false;
    }
    return true;
}

void dfs(int dep) {
    // a[1..m]
    if (ok) return;
    if (dep == m + 1) {
        ans.clear();
        ans = a;

        // check ans is valid
        ok = check(ans);
        return;
    }

    for (int i = 0; i < m; i++) if (!vis[i]) {
        a.push_back(buf[i]);
        vis[i] = true;
        dfs(dep + 1);
        a.pop_back();
        vis[i] = false;
    }
}

void init() {
    ok = false;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &m, &n) == 2 && m) {
        init();

        for (p = 1; p < n; p++) {
            prework();

            memset(vis, 0, sizeof(vis));
            a.clear();
            dfs(1);
            if (ok) {
                // output
                bool first = 1;
                for (int j = m - 1; j >= 0; j--) {
                    if (first) first = false;
                    else printf(" ");
                    printf("%d", ans[j]);
                }
                printf("\n");
                break;
            }
        }
        if (!ok) printf("Not found.\n");
    }
}

扫描线专题

扫描线求面积并

Atlantis

Atlantis

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
const int maxn = 1e4 + 5;
int n, m;

class segTree {
public:
    int l, r, cnt;
    double len;

    void clear() {
        l = r = 0;
        cnt = 0;
        len = 0;
    }
} tree[maxn * 8];

class A {
public:
    double x, y1, y2;
    int k;

    A() = default;
    A(double x, double y1, double y2, int k) : x(x), y1(y1), y2(y2), k(k) {}

    bool operator< (const A &rhs) const {
        return x < rhs.x;
    }
} a[maxn * 2];

vector<double> B;
map<double, int> ny;

void prework() {
    sort(a+1, a+1+m);

    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());

    for (auto x : B) ny[x] = lower_bound(B.begin(), B.end(), x) - B.begin();
}

void build(int p, int l, int r) {
    tree[p].clear();
    tree[p].l = l; tree[p].r = r;

    if (l == r) return;

    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1 | 1, mid + 1, r);
}

void pushup(int p) {
    if (tree[p].cnt) tree[p].len = B[tree[p].r + 1] - B[tree[p].l];
    else {
        if (tree[p].l == tree[p].r) tree[p].len = 0;
        else tree[p].len = tree[p<<1].len + tree[p<<1 | 1].len;
    }
}

void change(int p, int l, int r, int v) {
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].cnt += v;
        pushup(p);
        return;
    }

    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) change(p<<1, l, r, v);
    if (r > mid) change(p<<1 | 1, l, r, v);

    pushup(p);
}

void solve() {
    build(1, 0, B.size() - 2);

    double ans = 0.0;
    _rep(i, 1, m) {
        if (i > 1) ans += tree[1].len * (a[i].x - a[i-1].x);
        change(1, ny[a[i].y1], ny[a[i].y2] - 1, a[i].k);
    }
    printf("Total explored area: %.2f\n\n", ans);
}

void init() {
    m = 0;
    B.clear();
    ny.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;

    while (scanf("%d", &n) == 1 && n) {
        init();
        printf("Test case #%d\n", ++kase);

        // put data
        _rep(i, 1, n) {
            double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            a[++m] = A(x1, y1, y2, 1);
            a[++m] = A(x2, y1, y2, -1);
            B.push_back(y1);
            B.push_back(y2);
        }

        prework();
        solve();
    }
}

扫描线和格点

Acwing248
Acwing248

线段树的延迟标记常见的有以下几类

  • 将区间内的值全部增加 addadd
  • 将区间内的值重新设置 setset

注意延迟标记对 sum,maxv,minvsum, maxv, minv 等维护值的影响
另外还需注意，格点问题和上面的面积并问题的异同
Acwing248-02

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

const int maxn = 1e4 + 5;
int n, w, h;
int m = 0;

class segTree {
public:
    int l, r;
    int maxv, add;

    void clear() {
        l = r = 0;
        maxv = 0;
        add = 0;
    }
} tr[maxn * 8];

void build(int p, int l, int r) {
    tr[p].clear();
    tr[p].l = l; tr[p].r = r;

    if (l == r) return;

    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1 | 1, mid + 1, r);
}

void pushdown(int p) {
    if (tr[p].add) {
        int fl = tr[p].add;

        tr[p<<1].add += fl;
        tr[p<<1 | 1].add += fl;

        tr[p<<1].maxv += fl;
        tr[p<<1 | 1].maxv += fl;

        tr[p].add = 0;
    }
}

void pushup(int p) {
    tr[p].maxv = max(tr[p<<1].maxv, tr[p<<1 | 1].maxv);
}

void change(int p, int l, int r, int v) {
    if (l <= tr[p].l && tr[p].r <= r) {
        tr[p].add += v;
        tr[p].maxv += v;
        return;
    }

    pushdown(p);

    int mid = (tr[p].l + tr[p].r) >> 1;
    if (l <= mid) change(p<<1, l, r, v);
    if (r > mid) change(p<<1 | 1, l, r, v);

    pushup(p);
}

class A {
public:
    ll x, y1, y2;
    int c;
    A() = default;
    A(ll x, ll y1, ll y2, int c) : x(x), y1(y1), y2(y2), c(c) {}

    bool operator< (const A &rhs) const {
        return x < rhs.x || (x == rhs.x && c < rhs.c);
    }
} a[maxn * 2];

vector<ll> B;
map<ll, int> ny;
int ans = 0;

void prework() {
    sort(a+1, a+1+m);

    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    for (auto x : B) ny[x] = lower_bound(B.begin(), B.end(), x) - B.begin();
}

void solve() {
    build(1, 0, B.size()-1);

    _rep(i, 1, m) {
        change(1, ny[a[i].y1], ny[a[i].y2], a[i].c);
        //debug(a[i].c);
        chmax(ans, tr[1].maxv);
    }
    printf("%d\n", ans);
}

void init() {
    m = 0;
    B.clear();
    ny.clear();
    ans = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (~scanf("%d%d%d", &n, &w, &h)) {
        init();

        _rep(i, 1, n) {
            ll x, y;
            int c;
            scanf("%lld%lld%d", &x, &y, &c);
            //debug(c);

            a[++m] = A(x, y, y+h-1, c);
            a[++m] = A(x+w, y, y+h-1, -c);
            //debug(a[1].c);

            B.push_back(y);
            B.push_back(y+h-1);
        }

        // prework and solve
        prework();
        solve();
    }
}

扫描线求组合图形周长

HDU1828
HDU1828

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
const int maxn = 1e4 + 10;
int n, m[2];

class A {
public:
    int x, y1, y2, c;
    A() = default;
    A(int x, int y1, int y2, int c) : x(x), y1(y1), y2(y2), c(c) {}

    bool operator< (const A &rhs) const {
        return x < rhs.x || (x == rhs.x && c < rhs.c);
    }
} a[2][maxn];

vector<int> B[2];
map<int, int> ny[2];

void prework() {
    _for(i, 0, 2) {
        sort(a[i]+1, a[i]+1+m[i]);
        sort(B[i].begin(), B[i].end());
        B[i].erase(unique(B[i].begin(), B[i].end()), B[i].end());

        for (auto x : B[i]) ny[i][x] = lower_bound(B[i].begin(), B[i].end(), x) - B[i].begin();
    }
}

class segTree {
public:
    int l, r;
    int cnt;
    bool fl, fr;
    int cover;

    void clear() {
        l = r = 0;
        cnt = 0;
        fl = fr = false;
        cover = 0;
    }
} tr[maxn * 4];

void build(int p, int l, int r) {
    tr[p].clear();
    tr[p].l = l; tr[p].r = r;

    if (l == r) return;

    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1 | 1, mid + 1, r);
}

void pushup(int p, int sgn) {
    if (tr[p].cover) {
        tr[p].cnt = 1;
        tr[p].fl = tr[p].fr = 1;
    }
    else {
        if (tr[p].l == tr[p].r) {
            tr[p].fl = tr[p].fr = 0;
            tr[p].cnt = 0;
        }
        else {
            tr[p].fl = tr[p<<1].fl;
            tr[p].fr = tr[p<<1 | 1].fr;

            tr[p].cnt = tr[p<<1].cnt + tr[p<<1 | 1].cnt;
            if (tr[p<<1].fr && tr[p<<1 | 1].fl) tr[p].cnt--;
        }
    }
}

void change(int p, int l, int r, int v, int sgn) {
    if (l <= tr[p].l && tr[p].r <= r) {
        tr[p].cover += v;
        pushup(p, sgn);
        return;
    }

    int mid = (tr[p].l + tr[p].r) >> 1;
    if (l <= mid) change(p<<1, l, r, v, sgn);
    if (r > mid) change(p<<1 | 1, l, r, v, sgn);
    pushup(p, sgn);
}

int solve(int sgn) {
    build(1, 0, B[sgn].size() - 2);
    int ans = 0;

    _rep(i, 1, m[sgn]) {
        change(1, ny[sgn][a[sgn][i].y1], ny[sgn][a[sgn][i].y2]-1, a[sgn][i].c, sgn);
        //debug(ny[a[i].y1]);
        ans += 2 * tr[1].cnt * (a[sgn][i+1].x - a[sgn][i].x);
    }
    return ans;
}

int ans = 0;
void init() {
    memset(m, 0, sizeof(m));
    _for(i, 0, 2) {
        B[i].clear();
        ny[i].clear();
    }
    ans = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (~scanf("%d", &n)) {
        init();

        _rep(i, 1, n) {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
            a[0][++m[0]] = A(x1, y1, y2, 1);
            a[0][++m[0]] = A(x2, y1, y2, -1);
            B[0].push_back(y1);
            B[0].push_back(y2);

            a[1][++m[1]] = A(y1, x1, x2, 1);
            a[1][++m[1]] = A(y2, x1, x2, -1);
            B[1].push_back(x1);
            B[1].push_back(x2);
        }
        assert(m[0] == n*2 && m[1] == n*2);

        // prework
        prework();
        _for(i, 0, 2) ans += solve(i);
        printf("%d\n", ans);
    }
}