圆周上两点间的距离

[编程题]圆周上两点间的距离

热度指数：1197 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

定义圆周上两点的距离s为这两点之间的劣弧对应的圆心角度数(0<=s<=180)，现输入圆周上的n个点（n>=2），以角度a表示其位置(0<=a<360)，输入按a从小到大排序。求最远的一对点之间的距离。

输入描述:

第一行为点个数n(n≤100000)，后跟n行，每行一个双精度浮点数，表示点的角度（小数点后保留8位），例如输入样例中为4个点的输入

输出描述:

输出最远的一对点之间的距离（双精度浮点数，小数点后保留8位）和'\n'换行符。例如输入样例中，10.00000000与183.00000000两个点之间的距离为173.00000000，大于10.00000000与198.0000000之间的距离172.00000000，所以应输出：

173.00000000

示例1

输入

4
10.00000000
180.00000000
183.00000000
198.00000000

输出

173.00000000

备注:

注意事项：

1.程序性能要足够快，否则可能无法通过一些大型测试数据；

2.如果使用java语言，可以考虑使用BufferedReader从标准输入读取输入数据，Scanner读取一些比较大的输入数据会发生超时。

算法知识视频讲解

Python 3

觞乄默

题目的数据是错的。第一个测试点如果你跑出的结果是 179.00032571，说明你的代码没问题。

为什么这么说呢？因为我发现了数据里有两个点的距离等于 179.00032571，这个数大于给的预期输出（把第五行的0改成1，显示这两条数据）。这说明题目的数据有问题。

from bisect import bisect_left
a = []
for _ in range(int(input())):
    a.append(float(input()))
if 0:
    print(a[26634], a[46944], a[26634] - a[46944])
else:
    a.sort()
    ans = 0
    for x in a:
        x += 180 if x < 180 else -180
        i = bisect_left(a, x)
        if i == len(a):
            i = 0
        foo = 180 - min(abs(x - a[i]), abs(x - a[i-1]))
        if ans < foo:
            ans = foo
    print(f"{ans:.8f}")

发表于 2022-10-12 16:43:00 回复(0)