【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=XXXXXXXze();
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
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
chanyiushing
14年9个月前 IP:未同步
153707
源碼很黃,雖然我寫的也有點黃但會帶有一點藝術的暴力風格……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
h4x
14年9个月前 IP:未同步
154696
破囧3请自重。。
这种每个点都对比的算法效率也太低了。。
要是1W个点 程序直接爆掉

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

piapiapiapiapia~~!
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

所属专业
上级专业
同级专业
93°
学者 笔友
文章
651
回复
6032
学术分
30
2007/04/10注册,6年4个月前活动
暂无简介
主体类型:个人
所属领域:无
认证方式:邮箱
IP归属地:未同步
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}