33OJ
登录 注册

#P3091. [USACO13NOV] Line of Sight G

[USACO13NOV] Line of Sight G

题目描述

Farmer John 的 NN 头奶牛位于二维牧场中的不同点上。牧场中央有一个大型圆形谷仓。位于谷仓两侧、视线被谷仓挡住的奶牛无法互相看见。请计算有多少对奶牛可以通过直接视线互相看见。

谷仓是以原点 (0,0)(0,0) 为圆心、半径为 RR 的圆。没有奶牛位于谷仓对应的圆上或圆内,并且任意两头奶牛确定的直线都不会与谷仓相切。

输入格式

第一行包含两个整数:NN 和 RR。

接下来 NN 行,每行包含两个整数,表示一头奶牛的坐标 (x,y)(x,y)。

输出格式

输出一个整数,表示可以互相看见的奶牛对数。

4 5 
0 10 
0 -10 
10 0 
-10 0 

4 

提示

有 44 头奶牛,分别位于 (0,10)(0,10)、(0,−10)(0,-10)、(10,0)(10,0) 和 (−10,0)(-10,0)。谷仓以 (0,0)(0,0) 为圆心,半径为 55。

除了位于谷仓正对两侧的奶牛对外,其余所有奶牛对都可以互相看见:

  • (−10,0)(-10,0) 和 (10,0)(10,0) 无法互相看见;
  • (0,−10)(0,-10) 和 (0,10)(0,10) 无法互相看见。

总共有 66 对奶牛,其中 22 对被谷仓挡住,因此答案是 44。

数据范围

1≤N≤500001 \le N \le 50000

1≤R≤1061 \le R \le 10^6

∣x∣,∣y∣≤106|x|, |y| \le 10^6