文号
t19643
阅读
4254
回复
2
收藏
3
【C++ 轻H】寻找平面内最近的两个点
2009/09/13
IP:广东
一个基本算法,标准的欧几里得距离

BCB写的 首先是include


#include <math.h>
#include <vector>


using


using std::vector;


struct

struct point{
    public :
    int X;
    int Y;
};

struct p_result{
    public :
    point p1;
    point p2;
};


全局

vector<point> loli;

正题:C_point函数

p_result C_point(void){
    int i,j;
int dmin=10000;
double d;
int i1,i2;
int count;
count=loli.size();
point result;
point result2;

for (i = 0; i < count-1; i++) {
    for (j = i+1; j < count; j++) {

        int in1,in2;

        in1=pow((loli[i].X-loli[j].X),2);
        in2=pow((loli[i].Y-loli[j].Y),2);

        d = sqrt(in1+in2);

        if (d < dmin) {
            dmin = d;
            i1=i;
            i2=j;
        }
    }
}

result.X = loli[i1].X;
result.Y = loli[i1].Y;

result2.X = loli[i2].X;
result2.Y = loli[i2].Y;

p_result re;
re.p1 = result;
re.p2 = result2;

return (re);

}


我自重……

+1000
科创币
我说要有光
2009/09/13
开放有价值的源码
17年4个月前IP:未同步
153707
1楼
源碼很黃,雖然我寫的也有點黃但會帶有一點藝術的暴力風格……
引用
评论
17年3个月前IP:未同步
154696
2楼
破囧3请自重。。
这种每个点都对比的算法效率也太低了。。
要是1W个点 程序直接爆掉

正解应该是O(nlogn)的分治
每次求解的时候 分成左右两个区域 分别递归计算最近点对
然后合并的时候只要取左右最小点对和中间的8对点就够了
分治复杂度O(nlogn) 合并复杂度O(n)
因此总复杂度O(nlogn) 远低于您的O(n^2)

piapiapiapiapia~~!
引用
评论
笔记
{{note.content}}
{{n.user.username}}
{{fromNow(n.toc)}} {{n.status === noteStatus.disabled ? "已屏蔽" : ""}} {{n.status === noteStatus.unknown ? "正在审核" : ""}} {{n.status === noteStatus.deleted ? '已删除' : ''}}
  • 编辑
  • 删除
  • {{n.status === 'disabled' ? "解除屏蔽" : "屏蔽" }}
我也是有底线的