给定一组坐标,我想知道如何确定有多少个点在另外两个点之间。
A(1 ; 3)
B(2 ; 2)
C(3 ; 1)
D(3 ; 2)
E(3 ; 3)
这里是一个图示:
_______
|A| |E|
_______
| |B|D|
_______
| | |C|
_______
这里的B和D是中点,因此答案是“2”。
我找到了一个非常低效的O(n³)
算法。
count := 0
For each point x1
For each point x2
For each point x3
If x3 is the midpoint of [x1;x2]
count := count + 1
Print count
你有没有想过更高效的算法?