#P3663. Crazy Rabbit

    ID: 2858 传统题 2000ms 512MiB 尝试: 132 已通过: 81 难度: 8 上传者: 标签>难度分类提高+/省选-计算几何线段相交枚举与搜索暴力枚举排序与序列处理最长上升子序列耐心排序求 LIS极点极线对偶CF2400

Crazy Rabbit

[湖南集训] Crazy Rabbit

题目描述

城堡里有 nn 只兔子和一处圆形障碍。第 ii 只兔子位于 (xi,yi)(x_i,y_i)。圆心为原点,半径为 rr。

从中选出一些兔子,使任意两只选中的兔子所确定的整条直线都与圆形障碍没有交点。最多能选出多少只兔子?

输入格式

第一行两个整数 n,rn,r,分别表示兔子数和圆的半径。

接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示一只兔子的位置。所有兔子均严格位于圆外,任意两只兔子确定的直线都不会与圆相切。

输出格式

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

样例

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

例如,可以选第 1,2,4,61,2,4,6 只兔子。

六只兔子和圆形障碍的位置

数据范围

测试数据比例 nn 的范围
10%10\% 1≤n≤201\le n\le20
30%30\% 1≤n≤1001\le n\le100
100%100\% 1≤n≤20001\le n\le2000

半径满足 1≤r≤50001\le r\le 5000。坐标为整数,绝对值不超过 50005000。原样例含零坐标及负坐标。