logo AlgoBeat OnlineJudge
登录 注册

#104660. [BZOJ 4660] Crazy Rabbit

内存限制:512 MiB 时间限制:20000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

兔子们决定在自己的城堡里安排一些士兵进行防守。给出 n 个点的坐标,和城堡里一个圆心在原点的圆形的障碍

,兔子们希望从中选出 k 个兔子,使得它们两两所在的直线都不与圆相交。兔子们希望知道最多能选出多少兔子

输入格式

第一行两个整数 N 和 R, 表示兔子的个数和圆的半径接下来 N 行,每行两个整数 xi 和 yi ,表示第 i 只兔子

的坐标保证每只兔子都严格在障碍外部,且两两的所在的直线不与圆相切。

对于 100% 的测试数据, 1 <= n <= 2000; 1 <= R, xi, yi <= 5000

输出格式

输出一行一个整数, 表示最多能选出多少兔子

样例

样例输入

6 3
0 6
-7 -4
-3 -2
7 -5
-2 3
8 -3

样例输出

4
【样例1解释】
 选择第 1, 2, 6, 4 只兔子即可。