蓝桥杯 C\C++ 题目: 平面四点最小距离

已知平面上若干个点的坐标。需要求出在所有的组合中，4个点间平均距离的最小值（四舍五入，保留2位小数）。比如有4个点：a,b,c,d, 则平均距离是指：ab, ac, ad, bc, bd, cd 这6个距离的平均值。每个点的坐标表示为：横坐标,纵坐标,本题测试用例很多,达上千个点,要注意程序效率! 本文给出了C++语言的解法.

测试例中都是好几千个点,肯定不能全算,要缩小范围,可以分块,由1*1块开始,因为会有点重合,一但找到有4个点在同一块内,必在当前分组情况下存在最优解

对于分块:

由分块图可以看出,对于一个点(m,n),他会影响的分块极限:

左下角(焦点)落在x:m-w~m,y:n-w~n

即左下角方块中,所以可以遍历焦点在左下角方块范围的分块,而我恰好把焦点设置为分块数组下标,所以很方便,遍历下标为data[m-w][n-w]~data[m][n]把它们的计数+1,结束后,若有点>=4的分块,就存在最优解.

在分块中求解:

因为一个分块中可能不止4个点,所以要先对已经有的点按照下标升序全排列,然后遍历这个列表计算最小值,在当前分组下计算所有有可能的分块后再计算各个分块的最小值,这个最小值就是最终结果

效率:

因为分组区域是不断扩大的,所以数据越多效率越高,最坏情况下即只有4个点而且是四个角,要遍历1000^4次,当数据大于1000个时,应该可以在第一轮分组得到结果.

平面4点平均距离最小值C++解法