#P17197. PM957 最佳圆

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

PM957 最佳圆

题目描述

给定平面上的 nn 个点和一个整数半径 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

样例 3

5 2
1 1
1 3
1 5
3 1
3 5
3

样例 4

3 150
-100 -100
1 1
100 100
3

数据范围

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

说明

在样例 1 中,四个点是一个正方形的四个顶点。将圆心放在任意一条边的中点,可以覆盖该边的两个端点。

在样例 2 中,将圆心放在正方形的中心即可覆盖全部四个点。