Znzryb's Blog
0%

2026 杭电春季联赛 2——1005-守矢晨风（扫描线维护的激活集合可以应用差分思想， 这样只需要维护一个前缀激活集合即可）

Posted on Edited on

题目大意

题目描述

给定平面上 nn 个圆形区域，第 ii 个圆的圆心坐标为 (pi,qi)(p_i, q_i)，半径为 rir_i（保证 ri≤30r_i \le 30）。

给定 mm 次询问，每次询问给出一个四边平行于坐标轴的矩形区域，指定了其左下角顶点坐标 (xi,1,yi,1)(x_{i,1}, y_{i,1}) 和右上角顶点坐标 (xi,2,yi,2)(x_{i,2}, y_{i,2})。对于每次询问，需要计算出在给定的 nn 个圆中，有多少个圆与该矩形区域存在至少一个公共点。

数据范围

测试用例数量 tt 满足 1≤t≤10001 \le t \le 1000。
每次测试中的圆的个数 nn 满足 1≤n≤1.5×1061 \le n \le 1.5 \times 10^6，询问的个数 mm 满足 1≤m≤1041 \le m \le 10^4。
对于全部测试用例，保证 ∑n≤3×106\sum n \le 3 \times 10^6，∑m≤2×104\sum m \le 2 \times 10^4。
坐标与半径范围：1≤pi,qi≤1091 \le p_i, q_i \le 10^9，1≤ri≤301 \le r_i \le 30，1≤xi,1≤xi,2≤1091 \le x_{i,1} \le x_{i,2} \le 10^9，1≤yi,1≤yi,2≤1091 \le y_{i,1} \le y_{i,2} \le 10^9。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
4 1
1 1 1
7 1 2
5 3 2
1 2 1
2 2 6 4
8 3
5 6 4
7 7 4
3 3 2
1 8 5
10 1 2
1 8 1
7 2 2
5 4 5
9 1 10 5
3 1 6 3
5 1 9 5

样例输出

1
2
3
4
3
4
4
7

样例解释

在第一组测试数据中，共有 44 个圆和 11 次询问。询问给定的矩形左下角坐标为 (2,2)(2, 2)，右上角坐标为 (6,4)(6, 4)。经过判断，该矩形与输入的第 22 个圆、第 33 个圆以及第 44 个圆（总计三个圆形）存在公共点，因此该次询问的答案为 33。第二组测试数据同理，分别输出对应矩形内包含公共点的圆的数量。

image

思路讲解

这道题目应该是一道扫描线+树状数组，应该是不需要用到这个 K-D 树这种比较高级的东西的。

呃，那我们怎么做这道题目呢？首先就是用这个数据结构，快速求解出大矩形中的这个点，所谓的大矩形，就是矩形和圆的 minkowski 和（这个 minkowski 和是一个圆角矩形），当然，圆角矩形让我们用数据结构处理实在是，我们忽略其圆角，得到的就是所谓的“大矩形”（即图中黑色框框住的部分）。

小羊-2025-12-04-M. Ahmad’s Dish（圆和正多边形的这个 minkowski 和）（minkowski 和的交换不变性）

image

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）（把二维的问题变为一维的问题来做）

okay，我们上面的这个对扫描线总结的比较好。扫描线的重点就是维护一个当前生效的这个集合。按照一顺序排序后，那么我们其实就是要维护一个目前生效的圆的集合。

首先呢，就是这道题目，因为半径比较少，我们不妨把这个不同半径的圆分开处理。

然后因为我们目前把不同的半径分开处理，我们目前可以假设，所有的圆的这个半径都是相同的。我们就是像上面一样，把这个矩形扩大这个半径（👆想上面那个黑色的矩形一样）。

然后我们把矩形先按照 x 的右端点排序，再按照 x 的左端点排序。不过，我们发现，无论你怎么排序这个矩形和这个点（也就是这个圆心嘛），都很难维护一个严格生效的这个点的集合，主要也是矩形的是一个这个区间范围，无论怎么排都比较麻烦。

不过我们采用差分思想？其实就是如下方法：

左查询：在 X=Xmin−1X = X_{min} - 1 的时刻，查询树状数组中 [Ymin,Ymax][Y_{min}, Y_{max}] 区间的点数，记为 AA，从答案中减去 AA。（记录权重为 −1-1）

右查询：在 X=XmaxX = X_{max} 的时刻，查询树状数组中 [Ymin,Ymax][Y_{min}, Y_{max}] 区间的点数，记为 BB，加到答案中。（记录权重为 +1+1）

采用如上👆方法，我们只需要维护一个 [−INF,idx][-INF,idx] 的生效点集合就可以了，可以说是非常轻松惬意了，我们也不需要删除。

然后我们要进行这个几何点的这个扣除：

image

只要像上面👆一样，不断的枚举这个 dx，就可以排除掉所有的这个不合法的点。

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

struct Solve {
    ll N, M;
    Compress_<ll> li_y;
    vector<vector<X_y> > r_xy_ls;
    vector<Event> events_backup;
    vector<int> Ans;

    vector<Event> gen_event(ll r) {
        // vector<Event> tmp_events;
        vector<Event> events;
        // tmp_events.reserve(SZ(r_xy_ls[r]));
        for (auto [x,y]: r_xy_ls[r]) {
            events.push_back({x, y, Insert});
        }
        for (auto e: events_backup) {
            e.y1 -= r;
            e.y2 += r;
            if (e.type == Left) {
                e.x -= r;
            } else if (e.type == Right) {
                e.x += r;
            }
            events.push_back(e);
        }
        sort(all(events));
        return events;
    }

    void solve_single_r(ll r) {
        BIT tr(li_y.size());
        sort(all(r_xy_ls[r]));
        auto events = gen_event(r);
        for (auto &e: events) {
            if (e.type == Insert) {
                tr.add(li_y.get_i(e.y1), 1);
            } else if (e.type == Left) {
                Ans[e.id] -= tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
                Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y1+r,-1,-1);
                Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y2-r,-1,1);
            } else {
                Ans[e.id] += tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
                Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y1+r,1,-1);
                Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y2-r,1,1);
            }
        }
    }
		
		// 查找以这个 x 为首的，在范围 [ly,ry] 之间的这个点的数量
    ll query_r_x_l_r_cnt(ll r, ll x, ll ly, ll ry) {
        if (ly > ry) {
            return 0;
        }
        auto &xy_ls = r_xy_ls[r];
        auto itl = lower_bound(all(xy_ls), X_y{x, ly});

        if (itl == xy_ls.end()) {
            return 0;
        }
        if (itl->x != x) {
            return 0;
        }
        if (itl->y > ry) {
            return 0;
        }
        auto itr = upper_bound(all(xy_ls), X_y{x, ry});
        ll num = itr - itl;
        return num;
    }
		
		// 计算边缘的，可能被多算的这个点。
    ll redundant_circle_cnt(ll r, ll x, ll y, ll dirx, ll diry) {
        ll res = 0;
        for (int dx = 1; dx <= r; ++dx) {
            ll tox = x + dirx * dx;
            ll disy = sqrtl(r * r - dx * dx);
            ll toy = y + diry * disy;
            ll ly = min(toy + diry, y + diry * r);
            ll ry=max(toy + diry, y + diry * r);
            res += query_r_x_l_r_cnt(r, tox, ly, ry);
        }
        return res;
    }

    Solve() : r_xy_ls(32) {
        cin >> N >> M;
        li_y.reserve(N + M);
        // for (int i = 1; i <= 30; ++i) r_xy_ls[i].reserve(N);
        for (int i = 1; i <= N; ++i) {
            ll x, y, d;
            cin >> x >> y >> d;
            r_xy_ls[d].push_back({x, y});
            li_y.add(y);
        }
        events_backup.reserve(N + 30 * M);
        Ans.resize(M);
        for (int i = 0; i < M; ++i) {
            ll x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            for (int r = 0; r <= 30; ++r) {
                li_y.add(y1 - r, y2 + r);
            }
            events_backup.push_back({x1, y1, Left, i, y2});
            events_backup.push_back({x2, y1, Right, i, y2});
        }
        sort(all(events_backup));
        li_y.init();
        for (int i = 1; i <= 30; ++i) {
            solve_single_r(i);
        }
        for (int i = 0; i < M; ++i) {
            cout << Ans[i] << "\n";
        }
    }
};

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=19570

心路历程（WA，TLE，MLE……）

也是成功一次 AC 了，当然，在写一些模块的时候，ai 也帮助我进行了一些东西。