#P4206. 最大团

    ID: 3421 传统题 1000ms 256MiB 尝试: 185 已通过: 69 难度: 8 上传者: 标签>CF2400提高+/省选-最大团暴力枚举耐心排序求 LIS二分查找欧几里得算法极点极线对偶

最大团

题目描述

给出平面上 NN 个点的坐标,和一个半径为 RR 的圆心在原点的圆。对于两个点,它们之间有连边,当且仅当它们的连线与圆不相交。

求此图的最大团。

输入格式

第一行两个整数 NN 和 RR,表示点数和圆的半径。

接下来 NN 行,每行两个整数 xix_i 和 yiy_i,表示第 ii 个点的坐标。

保证每个点都严格在圆外,且两两直线不与圆相切。

输出格式

输出一个整数:最大团的大小。

样例

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

数据规模与约定

对于 100%100\% 的数据:1≤N≤2×1031\le N\le 2\times 10^3,∣xi∣,∣yi∣,R≤5×103|x_i|,|y_i|,R\le 5\times 10^3。