Searching_4

Description

Given n Magnets which are placed linearly, with each magnet to be considered as of point object. Each magnet suffers force from its left sided magnets such that they repel it to the right and vice versa. All forces are repulsive. The force being equal to the distance (1/d , d being the distance). Now given the positions of the magnets, the task to find all the points along the linear line where net force is ZERO.

Note: Distance have to be calculated with precision of 0.0000000000001.

Constraints:1<=T<=100,1<=N<=100,1<=M[]<=1000

（拍成一列的磁铁，相互作用的力与距离成反比（1/d)， 求其中作用力为0的点）

思路

距离越近，排斥力越大，所以每两个相邻磁铁之间都会出现一个作用力为0的点。

因此遍历每两个相邻位置的磁铁，找这两个磁铁之间作用力为0的点。

使用二叉搜索，时间复杂度O(nlogn)

按照题目的精度要求，在不同的oj系统中，可能会导致超时，所以可以试试大一点的精度。

python

def solve(mags):
    res = []
    for i in range(len(mags)-1):
        l, r = mags[i], mags[i+1]
        while True:
            mid = (l+r) / 2
            f = sum(1/(mid-m) for m in mags)
            if round(f, 5) == 0:
                res.append(mid)
                break
            elif f > 0:
                l = mid
            else:
                r = mid
    return res