题目描述
农民约翰的N头奶牛(1<=N<=50000头)位于其二维牧场的不同点上。牧场中间是一个巨大的圆形粮仓。筒仓两侧的奶牛看不见对方,因为筒仓挡住了它们的视线。请确定通过直接视线可以看到彼此的奶牛对的数量。
谷物筒仓以原点(0,0)为中心,半径为R。没有奶牛位于筒仓对应的圆上或圆内,也没有两头奶牛位于筒仓的切线上。R的值在1到1000000的范围内,每头牛都生活在一个整数坐标在1000000到1000000之间的点上。给定平面上的NNN个点,求有多少点对能互相看见而不被以原点为圆心,RR为半径的圆挡住。
题目保证不存在圆上或圆内的点,也不存在连接两点的线段为圆的切线。
1≤N≤50000
1\le R\le10^61≤R≤10^6
|x|,|y|\le10^6∣x∣,∣y∣≤10^6
输入格式
第1行:两个整数:N和R。
第2..1+N行:每行包含两个整数,指定奶牛的(x,y)坐标。
输出格式
第1行:可以看到彼此的成对奶牛的数量。
说明/提示
有4头奶牛位于(0,10)、(0,-10)、(10,0)和(-10,0)位置。筒仓以(0,0)为中心,半径为5。
除了位于筒仓相对两侧的奶牛外,所有6对奶牛都能看到对方:(-10,0)和(10,0)处的奶牛不能看到对方,(0,-10)和(0,10)处的牛不能看到对方。