在一道usaco的题上wa了三次。我也是厉害。
其实好像有简单做法的。不过我是要脑补一下曼哈顿最小生成树。
对于一个平面图上的点的曼哈顿最小生成树，一定存在一种方案，使得每个点的度数至多为8。也就是说以斜率为0,inf,1,-1的四条直线分出来的八个区域里各有一个点就行了。然后是可以保证的。
于是就是拿俩树状数组扫四遍就行了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
struct point {
int x, y, i;
point() {
x = -inf, y = -1;
}
point(int xo, int yo) {
x = xo, y = yo;
}
inline void init(int ix) {
scanf("%d%d", &x, &y);
i = ix;
}
};
inline bool operator <(const point& a, const point& b) {
return (a. x < b. x) || (a. x == b. x && a. y < b. y);
}
const int maxn = 100009;
const int maxx = 1e9;
int n, c, r[maxn], sz[maxn], cnt, msz;
int v[maxn], tv, w[maxn], tw;
point a[maxn], ta[maxn], tb[maxn];
int getRoot(int x) {
register int p, q;
for (p = r[x]; p ^ r[p]; p = r[p]);
for (; x ^ p; q = r[x], r[x] = p, x = q);
return x;
}
inline void join(int u, int v) {
r[getRoot(u)] = getRoot(v);
}
point btQry(point* t, int p) {
point s(-inf, -1);
for (++ p; p; p -= (p & -p))
if (s < t[p])
s = t[p];
return s;
}
void btChg(point* t, int p, point v) {
for (++ p; p < maxn; p += (p & -p))
if (t[p] < v)
t[p] = v;
}
inline bool isNeighbour(const point& a, const point& b) {
return abs(a. x - b. x) + abs(a. y - b. y) <= c;
}
void span() {
sort(a, a + n);
tv = tw;
for (int i = 0; i < n; ++ i) {
v[i] = a[i]. y - a[i]. x;
w[i] = - a[i]. x - a[i]. y;
}
sort(v, v + n);
tv = unique(v, v + n) - v;
sort(w, w + n);
tw = unique(w, w + n) - w;
for (int i = 1; i <= tv || i <= tw; ++ i)
ta[i] = tb[i] = point();
for (int i = 0; i < n; ++ i) {
int p(lower_bound(v, v + tv, a[i]. y - a[i]. x) - v);
point g(btQry(ta, p));
if (g. y > -1 && isNeighbour(a[i], a[g. y]))
join(a[i]. i, a[g. y]. i);
btChg(ta, p, point(a[i]. x + a[i]. y, i));
p = lower_bound(w, w + tw, - a[i]. x - a[i]. y) - w;
g = btQry(tb, p);
if (g. y > -1 && isNeighbour(a[i], a[g. y]))
join(a[i]. i, a[g. y]. i);
btChg(tb, p, point(a[i]. x - a[i]. y, i));
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &c);
for (int i = 0; i < n; ++ i) {
a[i]. init(i);
r[i] = i;
}
span();
for (int i = 0; i < n; ++ i)
a[i]. x = maxx - a[i]. x;
span();
for (int i = 0; i < n; ++ i)
swap(a[i]. x, a[i]. y);
span();
for (int i = 0; i < n; ++ i)
a[i]. x = maxx - a[i]. x;
span();
memset(sz, 0, sizeof(sz));
for (int i = 0; i < n; ++ i) {
if (r[i] == i)
++ cnt;
++ sz[getRoot(i)];
}
for (int i = 0; i < n; ++ i)
if (r[i] == i && sz[i] > msz)
msz = sz[i];
printf("%d %d\n", cnt, msz);
}
