#P17075. PM957 BestCircle

    ID: 16276 传统题 1000ms 64MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1600普及+/提高-有限候选集缩减暴力枚举圆相交平方距离比较

PM957 BestCircle

题目描述

平面上有 nn 个点,第 ii 个点的坐标为 (xi,yi)(x_i,y_i)。现在需要放置一个半径恰好为 rr 的圆,圆心可以位于平面上的任意实数坐标处。

如果一个点位于圆的内部或圆周上,就称这个点被该圆覆盖。

请你求出一个半径为 rr 的圆最多能够覆盖多少个给定点。

输入格式

第一行包含两个整数 n,rn,r,分别表示点的数量和圆的半径。

接下来 nn 行,每行包含两个整数 xi,yix_i,y_i,表示第 ii 个点的坐标。

输出格式

输出一个整数,表示半径为 rr 的圆最多能够覆盖的点数。

样例 1

4 2
1 1
1 5
5 1
5 5
2

样例 2

4 3
1 1
1 4
4 1
4 4
4

数据范围

  • 1≤n≤501\le n\le50;
  • −100≤xi,yi≤100-100\le x_i,y_i\le100;
  • 1≤r≤1501\le r\le150。

输入中的不同点允许具有相同坐标,此时它们仍应分别计数。

说明

圆心的坐标不要求为整数。

对于样例 1,四个点是一个正方形的四个顶点。可以将圆心放在正方形某条边的中点,从而覆盖这条边的两个端点。