记录编号	167840	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO Open08]牛的邻居	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.826 s
提交时间	2015-06-29 11:53:17	内存使用	3.75 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
#define Nil NULL
const int SIZEN=100010;
const int INF=0x7fffffff/2;
class Point{
public:
	int x,y;
	int id;
};
void print(const Point &p){
	cout<<"("<<p.x<<" "<<p.y<<")";
}
bool operator < (const Point &a,const Point &b){
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
int N;
int C;
Point P[SIZEN];
class Node{
public:
	int l,r;
	Node *lc,*rc;
	int t;
	void push_up(void){
		if(lc!=Nil){
			t=P[rc->t]<P[lc->t]?lc->t:rc->t;
		}
	}
	void modify(int x,int g){//新加一个横坐标为x的g号点
		if(x>r||x<l) return;
		if(x==l&&x==r){
			if(P[t]<P[g]) t=g;
		}
		else{
			lc->modify(x,g);
			rc->modify(x,g);
			push_up();
		}
	}
	int query(int a,int b){
		if(a>r||b<l) return 0;
		if(l>=a&&r<=b) return t;
		int g1=lc->query(a,b),g2=rc->query(a,b);
		return P[g2]<P[g1]?g1:g2;
	}
};
Node *build(int a,int b){
	Node *p=new Node;
	p->l=a,p->r=b;
	if(a==b){
		p->lc=p->rc=Nil;
		p->t=0;
	}
	else{
		int mid=(a+b)/2;
		p->lc=build(a,mid);
		p->rc=build(mid+1,b);
		p->t=0;
	}
	return p;
}
int ufs[SIZEN]={0};
int size[SIZEN]={0};
int grand(int x){
	return !ufs[x]?x:ufs[x]=grand(ufs[x]);
}
void merge(int a,int b){
	int ga=grand(a),gb=grand(b);
	if(ga==gb) return;
	ufs[ga]=gb;
	size[gb]+=size[ga];
}
int X[SIZEN];
Point Q[SIZEN];
void make_nearest(void){
	P[0].x=P[0].y=-INF;
	int tot=0;
	for(int i=1;i<=N;i++) X[tot++]=P[i].x;
	sort(X,X+tot);
	tot=unique(X,X+tot)-X;
	Node *root=build(0,tot-1);
	memcpy(Q,P,sizeof(Q));
	sort(Q+1,Q+1+N);
	for(int i=1;i<=N;i++){
		int l=lower_bound(X,X+tot,Q[i].x-C)-X;
		int r=upper_bound(X,X+tot,Q[i].x)-X-1;
		int q=root->query(l,r);
		if(q&&abs(P[q].y-Q[i].y)<=C) merge(Q[i].id,q);
		root->modify(lower_bound(X,X+tot,Q[i].x)-X,Q[i].id);
	}
}
void work(void){
	for(int i=1;i<=N;i++) size[i]=1;
	for(int c1=-1;c1<=1;c1+=2){
		for(int c2=-1;c2<=1;c2+=2){
			for(int i=1;i<=N;i++){
				P[i].x*=c1;
				P[i].y*=c2;
			}
			make_nearest();
		}
	}
	int cnt=0,mx=0;
	for(int i=1;i<=N;i++){
		if(ufs[i]==0){
			cnt++;
			mx=max(mx,size[i]);
		}
	}
	printf("%d %d\n",cnt,mx);
}
void read(void){
	scanf("%d%d",&N,&C);
	LL x,y;
	for(int i=1;i<=N;i++){
		scanf("%d%d",&x,&y);
		P[i].x=x+y,P[i].y=x-y;
		P[i].id=i;
	}
}
int main(){
	freopen("nabor.in","r",stdin);
	freopen("nabor.out","w",stdout);
	read();
	work();
	return 0;
}