hdu1007平面最近点对分治

题目大意:给你N对点,求这N对点中两队点的距离的一半,精确到小数点后两位

暴力显然O(n^2),不能过。

分治即可,对N对点对,求中间值,mid。按照横坐标升序排列,递归求出0到mid以及mid+1到N-1对点的最小距离。

分治关键步骤在合并。

我们求出两个最小距离,但是没有考虑一个点在左边,一个点在右边的情况。

 先求出两个最小距离中较小的一个,记为mdis

  根据mid点为分界点【mid-mdis,mid+mdis】的闭区间筛选出可能取得最小距离的点,因为平面上的点还包含纵坐标,所以水平

距离不在这个范围内不可能是最短距离。同理再对进入暂时数组(记为temp)的点对按纵坐标分类,再次筛选,并不断更新mdis

的值。

 #include <iostream> #include <cmath> #include <algorithm> using namespace std; struct Point{ double x,y; }; Point temp[100005];  Point point[100005];  bool cmpx(Point a,Point b) {     return a.x<b.x;  } bool cmpy(Point c,Point d) { return c.y<d.y;  } double dist(int t1,int t2) { return (pow((point[t1].x-point[t2].x),2)+pow((point[t1].y-point[t2].y),2));  }  double dis(int t1,int t2) { return (pow((temp[t1].x-temp[t2].x),2)+pow((temp[t1].y-temp[t2].y),2));  }  double dfs(int l,int r) { if(l+1==r)  return dist(l,r); if(l+2==r) return min(dist(l,r),min(dist(l,l+1),dist(l+1,r))); int mid=(l+r)>>1;  double leftmindis=dfs(l,mid);  double rightmindis=dfs(mid+1,r); double mdis=min(leftmindis,rightmindis); int tot=0; for(int i=l;i<=r;i++)     if(point[i].x<=point[mid].x+mdis&&point[i].x>=point[mid].x-mdis)      temp[tot++]=point[i];      sort(temp,temp+tot,cmpy);    for(int i=0;i<tot;i++)        for(int j=i+1;j<tot;j++)           if(temp[j].y-temp[i].y>=mdis) break;           else mdis=min(dis(i,j),mdis); return mdis; } int main() { int N; while(cin>>N&&N)  { for(int i=0;i<N;i++)   { scanf("%lf%lf",&point[i].x,&point[i].y);   }   sort(point,point+N,cmpx);   double ans=sqrt(dfs(0,N-1))/2;    printf("%.2lf\n",ans); } return 0; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

左手用R右手Python系列——因子变量与分类重编码

今天这篇介绍数据类型中因子变量的运用在R语言和Python中的实现。 因子变量是数据结构中用于描述分类事物的一类重要变量。其在现实生活中对应着大量具有实际意义的...

3995
来自专栏数据结构与算法

线性代数学习笔记(代数版)

\(A^T\)表示矩阵的转置,即\(a_{ij}^{T} = a_{ji}\),相当于把矩阵沿主对角线翻转

1114
来自专栏人工智能

十五:多层感知机与布尔函数

今天没有别的话,好好学习,多多转发! 本期内容是 【多层感知机与布尔函数】 场景描述 神经网络概念的诞生很大程度上受到了神经科学的启发。生物学研究表明,大脑皮层...

2998
来自专栏大数据挖掘DT机器学习

CART算法学习及代码实现

1.算法介绍 分类回归树算法:CART(Classification And Regression Tree)算法采用一种二分递归分割的技术,将当前的样...

4714
来自专栏人工智能

人工智能AI(5):线性代数之矩阵、线性空间

在前面的篇幅中,我们简单的介绍过矩阵的定义,按照原计划本来,今天准备写特征分解以及奇异值分解,但是发现这其中涉及到比较多的矩阵相关的知识,所以在讨论这些问题之前...

2735
来自专栏小樱的经验随笔

算法--枚举策略

枚举法的基本思想 枚举法的基本思想是根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的。能使命题成立,即为其解。 枚举结构:循环...

5129
来自专栏计算机视觉life

SLIC超像素分割详解(二):关键代码分析

SLIC超像素分割详解(二) 网站http://ivrl.epfl.ch/research/superpixels给出了SLIC的代码。对于其中C++代码的几个...

2547
来自专栏ArrayZoneYour的专栏

如何用Python将时间序列转换为监督学习问题

像深度学习这样的机器学习方法可以用于时间序列预测。

1.7K10
来自专栏深度学习自然语言处理

基于attention的seq2seq机器翻译实践详解

理理思路 文本处理,这里我是以eng_fra的文本为例,每行是english[tab]french,以tab键分割。获取文本,清洗。 分别建立字典,一个engl...

5306
来自专栏PPV课数据科学社区

【工具】SAS 常用函数汇总

? 一、数学函数 ABS(x) 求x的绝对值。 MAX(x1,x2,…,xn) 求所有自变量中的最大一个。 MIN(x1,x2,…,xn) 求所有自变量...

2673

扫码关注云+社区

领取腾讯云代金券