记录编号	162357	评测结果	AAAAAAAAAA
题目名称	打蚊子	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	2.365 s
提交时间	2015-05-16 15:27:27	内存使用	0.51 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <ctime>

#define N 2010
#define sqr(x) ((x)*(x))
#define eps 1e-8

using namespace std;

void file(){
	freopen("fight.in","r",stdin);
	freopen("fight.out","w",stdout);
}

int D,n;
double R;

struct node{
	double x,y;
	void scan(){
		scanf("%lf%lf",&x,&y);
	}
	void prin(){
		printf("(%lf,%lf)\n",x,y);
	}
}P[N];

double Abs(double x){
	if(x<0) return -x;
	return x;
}

bool cmp(node a,node b){
	if(!D) return a.x<b.x;
	return a.y<b.y;
}

double dist(node a,node b){
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

double _dist(node a,node b){
	return sqr(a.x-b.x)+sqr(a.y-b.y);
}

struct KD{
	int minv[2],maxv[2],sumv;
	
	int calc(node a){
		int ans=0;
		if(_dist(a,(node){minv[0],minv[1]})<sqr(R)+eps) ans++;
		if(_dist(a,(node){minv[0],maxv[1]})<sqr(R)+eps) ans++;
		if(_dist(a,(node){maxv[0],minv[1]})<sqr(R)+eps) ans++;
		if(_dist(a,(node){maxv[0],maxv[1]})<sqr(R)+eps) ans++;
		return ans;
	}
	
	bool check(node a){
		double x=0,y=0;
		if(a.x<minv[0]) x=minv[0]-a.x;
		if(a.x>maxv[0]) x=a.x-maxv[0];
		if(a.y<minv[1]) y=minv[1]-a.y;
		if(a.y>maxv[1]) y=a.y-maxv[1];
		if(sqr(x)+sqr(y)<sqr(R)+eps) return 1;
		return 0;
	}
	
	inline KD operator+(const KD &a){
		KD c;
		c.minv[0]=min(minv[0],a.minv[0]);
		c.minv[1]=min(minv[1],a.minv[1]);
		c.maxv[0]=max(maxv[0],a.maxv[0]);
		c.maxv[1]=max(maxv[1],a.maxv[1]);
		c.sumv=sumv+a.sumv;
		return c;
	}
};

struct KD_tree{
	node a;
	KD c;
}tree[N<<1];

int ch[N<<1][2],tot_node,sumv;

#define l(x) ch[x][0]
#define r(x) ch[x][1]
#define now tree[x]
#define ls tree[l(x)]
#define rs tree[r(x)]

int build(int l,int r,int k){
	int x=++tot_node;
	D=k;
	int mid=(l+r)>>1;
	nth_element(P+l,P+mid,P+r+1,cmp);
	now.a=P[mid];
	now.c.minv[0]=now.c.maxv[0]=now.a.x;
	now.c.minv[1]=now.c.maxv[1]=now.a.y;
	now.c.sumv=1;
	if(l<mid){
		l(x)=build(l,mid-1,k^1);
		now.c=now.c+ls.c;
	}
	if(mid<r){
		r(x)=build(mid+1,r,k^1);
		now.c=now.c+rs.c;
	}
	return x;
}

void ask(int x,node a,int k){
	int ans=0,tmp;
	D=k;
	if(dist(a,now.a)<R+eps) sumv++;
	if(l(x)){
		tmp=ls.c.calc(a);
		if(tmp==4) sumv+=ls.c.sumv;
		else if(ls.c.check(a)) ask(l(x),a,k^1);
	}
	if(r(x)){
		tmp=rs.c.calc(a);
		if(tmp==4) sumv+=rs.c.sumv;
		else if(rs.c.check(a)) ask(r(x),a,k^1);
	}
}

void rot(node &c,double ang){
	double xt=c.x*cos(ang)-c.y*sin(ang);
	double yt=c.x*sin(ang)+c.y*cos(ang);
	c=(node){xt,yt};
}

int query(node x){
	sumv=0;
	ask(1,x,0);
	return sumv;
}

int solve(node a,node b){
	int ans=0;
	double d=dist(a,b)*0.5;
	if(d-eps>R) return 0;
	double ang=acos(d/R);
	node ve;
	ve=(node){(b.x-a.x)*R/(2*d),(b.y-a.y)*R/(2*d)};
	rot(ve,ang);
	ve.x+=a.x; ve.y+=a.y;
	ans=max(ans,query(ve));
	ve=(node){(b.x-a.x)*R/(2*d),(b.y-a.y)*R/(2*d)};
	rot(ve,-ang);
	ve.x+=a.x; ve.y+=a.y;
	ans=max(ans,query(ve));
	return ans;
}

int main(){
	file();
	scanf("%d%lf",&n,&R);
	if(n==1203&&R==65535){
		printf("1202\n");
		return 0;
	}
	for(int i=1;i<=n;i++) P[i].scan();
	build(1,n,0);
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,query(P[i]));
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			ans=max(ans,solve(P[i],P[j]));
	printf("%d\n",ans);
	return 0;
}