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

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

来源: 石博文博客 | 浏览: 2224 | 评论: 2 发表时间: 2013-04-10

已知平面上若干个点的坐标。需要求出在所有的组合中,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++解法



  • 声明: 评论属于其发表者所有,不代表本站的观点和立场.
  • 保元汤 回复该留言 时间: 2013-04-16

    来支持一下博主。看到代码就头晕!!

  • 四物汤 回复该留言 时间: 2013-05-04

    这一堆代码呀!!貌似很高深!!来看看!

已有 2 位网友发表了一针见血的评论,你还等什么?
  • 昵称: *
  • 邮箱:
  • 网址:
  • 记住我的信息
  • Color
  • Red
  • Blue
  • Code
  • bash
  • cpp
  • css
  • java
  • js
  • perl
  • php
  • python
  • ruby
  • sql
  • xml