翻译
查看原帖
翻译
1072488
KefaKabuqinuo楼主2023/12/3 14:54

题目描述

农民约翰的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)处的牛不能看到对方。

2023/12/3 14:54
加载中...