Skip to content

洛谷 - P2906 Cow Neighborhoods G

题解约 1.1 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

测试数据可以在 Luogu/P2906/data 目录下获得,与洛谷上的测试点顺序有偏差。

题面

题目描述

了解奶牛的人都知道奶牛是如何组成「奶牛社区」的。他们观察了 Farmer John 的 NN 头奶牛(编号为 1N1 \sim N),它们在 XXYY 坐标范围为 11 的牧场上放牧,每头奶牛都在自己唯一的整数直线坐标上。

如果满足以下两个标准中的至少一个,则两头奶牛是邻居:

  1. 两只奶牛的曼哈顿距离不超过 CC,即 Xixi+YiyiC|X_i - x_i| + |Y_i - y_i| \leq C
  2. 两只奶牛有共同的邻居。即存在一只奶牛 kk,使 iikkjjkk 均同属一个群。

给定奶牛的位置和距离 CC,确定「奶牛社区」的数量和最大的「奶牛社区」中的奶牛数量。

例如,考虑下面的牧场。 当 C=4C = 4 时,这个牧场有四个社区:左边的一个大社区,两个大小为 1 的社区,右边有一个巨大的社区,里面有 6060 头不同的奶牛。

.....................................*.................
....*...*..*.......................***.................
......*...........................****.................
..*....*..*.......................*...*.******.*.*.....
........................*.............***...***...*....
*..*..*...*..........................*..*...*..*...*...
.....................................*..*...*..*.......
.....................................*..*...*..*.......
...*................*..................................
.*..*............................*.*.*.*.*.*.*.*.*.*.*.
.*.....*..........................*.*.*.*.*.*.*.*.*.*.*
....*..................................................

输入格式

11 行包含两个用空格分隔的整数 N,CN, C

22 到第 N+1N + 1 行每行包含两个用空格分隔的整数 Xi,YiX_i, Y_i,表示一头牛的坐标。

输出格式

共一行,为两个用空格分隔的整数,为「奶牛社区」的数量和最大的「奶牛社区」内牛的数量。

输入输出样例

样例输入 #1

4 2
1 1
3 3
2 2
10 10

样例输出 #1

2 3

样例说明 #1

样例中有 22 个社区,一个由前三头奶牛组成,另一个是最后一头奶牛。因此,最大的社区大小为 33

数据范围与约定

对于 100%100\% 的数据,1N1051 \leq N \leq 10^51C1091 \leq C \leq 10^91Xi,Yi1091 \leq X_i, Y_i \leq 10^9Xi,YiX_i, Y_i 均为整数。

思路

机房巨佬于队曾经教过我们一个小 trick:曼哈顿距离和切比雪夫距离之间的转化。

曼哈顿坐标系是通过将切比雪夫坐标系旋转 π4\frac{\pi}{4} 后再缩小到原来的一半得到的。那么可以通过将 (x,y)(x, y) 变为 (x+y,xy)(x + y, x - y) 得到曼哈顿坐标系。

记题中第 ii 个点 (Xi,Yi)(X_i, Y_i) 的切比雪夫坐标为 (xi,yi)(x_i, y_i),那么限制 11 可以改写成:

  • 两只奶牛的切比雪夫距离不超过 CC,即 max(x1x2,y1y2)C\max(|x_1 - x_2|, |y_1 - y_2|) \leq C

那么可以先以 xx 轴坐标为第一关键字,yy 轴坐标为第二关键字从小到大排序,并使用并查集合并同一群的奶牛。然后使用 set 维护 yy 轴坐标的值,在插入每个点之前将 xx 轴坐标不合法的删除,然后使用 lower_bound 找到 yiy_i 的前驱和后继,如果满足限制则将其与 yiy_i 合并。最后统计连通块个数和最大连通块大小即可。

代码

#include <iostream>
#include <algorithm>
#include <set>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, c, fa[N], cnt[N], ans, max;
std::pair<int, int> points[N];
std::set<std::pair<int, int>> set;

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline void merge(int x, int y) {
    fa[find(x)] = find(y);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> c;

    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y;

        points[i] = std::make_pair(x + y, x - y);
        fa[i] = i;
    }

    std::sort(points + 1, points + 1 + n);

    set.insert(std::make_pair(points[1].second, 1));
    for (int i = 2, l = 1; i <= n; i++) {
        while (points[i].first - points[l].first > c) {
            set.erase(std::make_pair(points[l].second, l));
            l++;
        }

        auto it = set.lower_bound(std::make_pair(points[i].second, 0));

        if (it != set.end() && it->first - points[i].second <= c) {
            merge(i, it->second);
        }

        if (it != set.begin() && points[i].second - (--it)->first <= c) {
            merge(i, it->second);
        }

        set.insert(std::make_pair(points[i].second, i));
    }

    for (int i = 1; i <= n; i++) {
        if (find(i) == i) ans++;

        max = std::max(max, ++cnt[find(i)]);
    }

    cout << ans << ' ' << max << endl;

    return 0;
}