Toggle navigation
科创
{{ getSearchSuggestionLabel(suggestion) }}
{{ part.text }}
查看更多
登录
 
注册
电波
论坛
专栏
应用
登录
注册
{{ getSearchSuggestionLabel(suggestion) }}
{{ part.text }}
查看更多
论坛
>
计算机科学
>
软件综合
文号
t19643
阅读
4254
回复
2
收藏
3
【C++ 轻H】寻找平面内最近的两个点
93°
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
开放有价值的源码
来自:
计算机科学
/
软件综合
2
0
全部
只看作者
chanyiushing
17年4个月前
IP:未同步
153707
1楼
源碼很黃,雖然我寫的也有點黃但會帶有一點藝術的暴力風格……
加载全文
引用
评论
0
h4x
17年3个月前
IP:未同步
154696
2楼
破囧3请自重。。
这种每个点都对比的算法效率也太低了。。
要是1W个点 程序直接爆掉
正解应该是O(nlogn)的分治
每次求解的时候 分成左右两个区域 分别递归计算最近点对
然后合并的时候只要取左右最小点对和中间的8对点就够了
分治复杂度O(nlogn) 合并复杂度O(n)
因此总复杂度O(nlogn) 远低于您的O(n^2)
piapiapiapiapia~~!
加载全文
引用
评论
0
全部
只看作者
在列表中查看
笔记
{{note.content}}
{{n.user.username}}
{{fromNow(n.toc)}} {{n.status === noteStatus.disabled ? "已屏蔽" : ""}} {{n.status === noteStatus.unknown ? "正在审核" : ""}} {{n.status === noteStatus.deleted ? '已删除' : ''}}
编辑
删除
{{n.status === 'disabled' ? "解除屏蔽" : "屏蔽" }}
保存
取消
我也是有底线的
保存中...
保存