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

Posted on Symbols count in article: 762 Reading time ≈ 3 mins.

Problem

【USACO2008 Open】奶牛的邻居

Time  Limit:  5  Sec\mathrm{Time\;Limit:\;5\;Sec}
Memory  Limit:  64  MB\mathrm{Memory\;Limit:\;64\;MB}

Description

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N  (1≤N≤105)N\;(1\le N\le10^5)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标xi,yi  (xi,yi∈[1,109],xi,yi∈Z)x_i,y_i\;(x_i,y_i\in[1,10^9],x_i,y_i\in\Z)．当满足下列两个条件之一，两只奶牛ii和jj是属于同一个群的：

  1. 两只奶牛的曼哈顿距离不超过C  (1≤C≤109)C\;(1\le C\le10^9)，即∣xi−xj∣+∣yi−yj∣≤C|x_i-x_j|+|y_i-y_j|\le C.
  2. 两只奶牛有共同的邻居，即存在一只奶牛kk，使ii与k，jk，j与kk均同属一个群．

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

Input

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

Output

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

Sample Input

1
2
3
4
5
4 2
1 1
3 3
2 2
10 10

Sample Output

1
2 3

Source

Gold

标签：计算几何 set

Solution

对于原来的点(x,y)(x,y)，将其转化为(x+y,x−y)(x+y,x-y)，则其原来的曼哈顿距离转化为切比雪夫距离，即max⁡(∣xi−xj∣,∣yi−yj∣)\max(|x_i-x_j|,|y_i-y_j|)。这样xx和yy就无关了。两个点能相连当且仅当转换坐标后∣xi−xj∣≤C,∣yi−yj∣≤C|x_i-x_j|\le C,|y_i-y_j|\le C。
将所有点转换坐标后以xx从小到大排序，这样可以用双指针维护xx值之差不超过CC的一段区间。同时对在这段区间中的点用一个set\mathrm{set}维护其yy坐标，若新加入的点与其前驱后继的差不超过CC，则分别连边。用并查集维护连通块个数和大小即可。

Code

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
#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;
}