BZOJ1604【USACO2008 Open】奶牛的邻居 < 计算几何+set >

Problem

【USACO2008 Open】奶牛的邻居

Description

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标．当满足下列两个条件之一，两只奶牛和是属于同一个群的：

1. 两只奶牛的曼哈顿距离不超过，即.
2. 两只奶牛有共同的邻居，即存在一只奶牛，使与与均同属一个群．

给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛。

Input

第行输入和，之后行每行输入一只奶牛的坐标。

Output

仅一行，先输出牛群数，再输出最大牛群里的牛数，用空格隔开。

Sample Input

4 2
1 1
3 3
2 2
10 10

Sample Output

2 3

Source

Gold

标签：计算几何 set

Solution

对于原来的点，将其转化为，则其原来的曼哈顿距离转化为切比雪夫距离，即。这样和就无关了。两个点能相连当且仅当转换坐标后。
将所有点转换坐标后以从小到大排序，这样可以用双指针维护值之差不超过的一段区间。同时对在这段区间中的点用一个维护其坐标，若新加入的点与其前驱后继的差不超过，则分别连边。用并查集维护连通块个数和大小即可。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, fa[MAX_N+5], sz[MAX_N+5]; lnt m;
struct pnt {int id; lnt x, y;} p[MAX_N+5];
bool cmp(pnt a, pnt b) {return a.x < b.x;}
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
bool operator < (pnt a, pnt b) {return a.y == b.y ? a.x < b.x : a.y < b.y;}
void merge(int u, int v) {if ((u = getf(u)) ^ (v = getf(v))) fa[v] = u, sz[u] += sz[v];}
int main() {
    read(n), read(m);
    deque <pnt> que; set <pnt> s;
    s.insert((pnt){0, INF, INF});
    s.insert((pnt){0, -INF, -INF});
    for (int i = 1, x, y; i <= n; i++)
        read(x), read(y), p[i].x = x+y, p[i].y = x-y;
    for (int i = 1; i <= n; i++) p[i].id = fa[i] = i, sz[i] = 1;
    sort(p+1, p+n+1, cmp), que.push_back(p[1]), s.insert(p[1]);
    for (int i = 2; i <= n; i++) {
        que.push_back(p[i]);
        while (que.back().x-que.front().x > m)
            s.erase(s.find(que.front())), que.pop_front();
        set <pnt> :: iterator pre, suc;
        pre = suc = s.lower_bound(p[i]), pre--;
        if (p[i].y-(*pre).y <= m) merge(p[i].id, (*pre).id);
        if ((*suc).y-p[i].y <= m) merge(p[i].id, (*suc).id);
        s.insert(p[i]);
    }
    int cnt = 0, mx = 0;
    for (int i = 1; i <= n; i++)
        if (getf(i) == i) cnt++, mx = max(mx, sz[i]);
    return printf("%d %d\n", cnt, mx), 0;
}