<div class="post_brief"><p>
在一道usaco的题上wa了三次。我也是厉害。</p>

 

其实好像有简单做法的。不过我是要脑补一下曼哈顿最小生成树。

 

对于一个平面图上的点的曼哈顿最小生成树,一定存在一种方案,使得每个点的度数至多为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", &amp;n, &amp;c);
for (int i = 0; i &lt; n; ++ i) {
	a[i]. init(i);
	r[i] = i;
}
span();
for (int i = 0; i &lt; n; ++ i)
	a[i]. x = maxx - a[i]. x;
span();
for (int i = 0; i &lt; n; ++ i)
	swap(a[i]. x, a[i]. y);
span();
for (int i = 0; i &lt; n; ++ i)
	a[i]. x = maxx - a[i]. x;
span();
memset(sz, 0, sizeof(sz));
for (int i = 0; i &lt; n; ++ i) {
	if (r[i] == i)
		++ cnt;
	++ sz[getRoot(i)];
}
for (int i = 0; i &lt; n; ++ i)
	if (r[i] == i &amp;&amp; sz[i] &gt; msz)
		msz = sz[i];
printf("%d %d\n", cnt, msz);

}