#P4660. Crazy Rabbit

    ID: 3794 传统题 2000ms 512MiB 尝试: 115 已通过: 66 难度: 8 上传者: 标签>难度分类提高+/省选-枚举与搜索暴力枚举排序与序列处理耐心排序求 LIS模拟与实现技巧坐标变换计算几何极点极线对偶CF2400

Crazy Rabbit

[湖南集训] Crazy Rabbit

题目描述

兔子们要在城堡里安排士兵。城堡中有一个以原点为圆心、半径为 rr 的圆形障碍,给出 nn 只兔子的坐标。

从这些兔子中选出尽可能多的兔子,使任意两只被选中的兔子所确定的整条直线都与圆没有公共点。求最多可以选出多少只兔子。

输入格式

第一行两个整数 n,rn,r。接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示第 ii 只兔子的坐标。

保证每只兔子都严格在圆外,且任意两只兔子所确定的直线都与圆不相切。

输出格式

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

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

样例解释

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

样例中六只兔子、圆形障碍及所选兔子之间的连线

数据范围

对于 10%10\% 的数据,1≤n≤201\le n\le20。对于 30%30\% 的数据,1≤n≤1001\le n\le100。

对于全部数据,1≤n≤20001\le n\le2000,1≤r≤50001\le r\le5000,−5000≤xi,yi≤5000-5000\le x_i,y_i\le5000。