应该是较准确的翻译
查看原帖
应该是较准确的翻译
958338
Lieyiqi楼主2023/11/21 21:38

题目描述

Farmer John的 NN 只奶牛 (1<=N<=50000)(1 <= N <= 50000) 位于他的二维牧场的不同点。在牧场的中心是一个大圆形储粮筒。位于储粮筒两侧的奶牛不能相互看到,因为储粮筒挡住了它们的视线。请确定直接视线可以看到彼此的奶牛对数。

储粮筒以原点 (0,0)(0,0)为中心,半径为 RR。没有奶牛位于或在对应于储粮筒的圆内,也没有两只奶牛位于储粮筒的切线上。RR 的值范围为 1...10000001...1000000 ,每只奶牛都生活在坐标范围在 −1000000..+1000000-1000000..+1000000 之间的点。

1≤N≤500001≤N≤50000

1≤R≤1061≤R≤10^6

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

输入格式

输入第一行两个整数:NN 和 RR

第二行至 N+1N+1 行,每行包含两个整数,指定一只奶牛的 (x,y)(x,y) 坐标

输出格式

输出一行,表示可以相互看到的奶牛对数

输入输出样例

输入#1

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

输出#1

4

说明/提示

有四只奶牛位于 (0,10),(0,−10),(10,0)(0,10),(0,-10),(10,0) 和 (−10,0)(-10,0)处。储粮筒位于 (0,0)(0,0) 处,半径为5。

除了位于储粮筒两侧的奶牛对(位于 (−10,0)(-10,0) 和 (10,0)(10,0) 处的奶牛,以及位于 (0,−10)(0,-10) 和 (0,10)(0,10)处的奶牛)不能相互看到外,所有6对奶牛都可以相互看到。

2023/11/21 21:38
加载中...