视线
Description
二维平面上,原点处有一个半径为R的圆。平面上有N个点,保证没有点在圆上或圆内,保证任意两个点不与圆相切,求互相可以看见的点的对数。
看见:对于两个点(x1, y1)和(x2, y2),他们的线段与圆没有交点。
计算对数时,(a, b)和(b, a)视为相同,且(a,a)不算点对。
Format
Input
第一行,两个整数N,R。
第2~N+1行,每行两个整数,表示点的坐标。
Output
一行,一个整数,表示能互相看见的点的对数。
Sample 1
Input
4 5
0 10
0 -10
10 0
-10 0
Output
4
样例解释:
有一个半径为5的圆。
总共有C(4, 2)= 6个对数。其中有两个点对不满足“看见”:
(-10, 0)和(10, 0)
(0, 10) 和 (0, -10)
Limitation
对于40%的数据,N <= 1000。
对于100%的数据, N <= 50000。
点的坐标为[-10^6, 10^6]内的整数。
R的取值为[1, 10^6]内的整数。
1s, 256MiB for each test case.
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 2
- 已通过
- 1
- 通过率
- 50%
- 上传者