题目大意:

给定一堆点集,在这一堆点集中找到一组点集它们之间的距离达到最短

对于HDU1007因为求圆的半径,所以距离还要除以2

普通情况下,可以将nge点,将任意两个点之间的距离都算一遍,在循环过程中,每次取到距离的较小值

但数据量大的话,这种O(n^2)的方法肯定是不合理的

转化为O(nlogn)的方法是可取的

这里采用分治的方法

我们希望尽可能的均匀分配,也就是让左右两端所含有的点的数目一样多,所以一开始就根据以x优先排序 , 然后取中值作为分割边

int fenzhi(int l , int r)

{

  int m = (l+r) >> 1;

  int d1 = fenzhi(l , m);

  int d2 = fenzhi(m+1 , r);

  int d3 = 左右两部分的点相互作距离运算得到  //也就是一个合并的过程

  return min(d1 , d2 , d3);

}

当l == r时 无疑距离不存在,我们返回一个最大值maxn即可不会影响结果

当l == r-1说明只存在两个点, 那就是将这两个点的距离作为最短距离返回即可

由于是自底向下

我们可以根据d1 , d2 , 优先得到d = min(d1 , d2)

那样我们在合并的过程中只要找距离小于d的点就可以了,我们不能将所有点都访问一遍,但是我们可以控制一个范围

先找到所有离分割线距离小于d的点,也即左侧的图所示,超出那个范围的话必然左右两个点相连距离大于d

找到所有符合点将其下标用rec数组保存即可

然后将rec数组中的点全都比较一遍,比较过程中可以先只关注两点在y轴上的距离是否小于d , 是的话计算距离,并且与原距离取最小值

 #include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
#define maxn 2000000000 struct Point{
double x , y;
//利用减法运算计算两点间的距离
double operator-(const Point &m)const{
return sqrt((x-m.x)*(x-m.x) + (y-m.y)*(y-m.y));
}
}p[N]; bool cmpxy(const Point &m1 , const Point &m2){
if(m1.x == m2.x) return m1.y < m2.y;
return m1.x < m2.x;
} //d要随之更改,所以参数要引用传递
void merge_l_r(double &d , int l , int r)
{
int m = (l+r) >> ;
/*得到所有离分割线距离不大于d的点,否则本身到分割线就大于d,那么左右两侧相连必然大于d
就没有保留下去的必要了*/
int rec[N] , k = ;//记录所有符合点的编号
for(int i = l ; i<=r ; i++){
if(p[m] - p[i] < d)
rec[k++] = i;
} //有见到别人博客在这里将rec根据对应点的y的大小排了一次序,但我提交了好像时间反而更长就干脆不用了
/*
大致如下:
现在最外面写个
bool cmpxy(const Point &m1 , const Point &m2){
if(m1.x == m2.x) return m1.y < m2.y;
return m1.x < m2.x;
}
这个位置写个sort(rec , rec+k , cmpy);
*/
for(int i= ; i<k ; i++){
for(int j=i+ ; j<k ; j++){
if(abs(p[rec[j]].y - p[rec[i]].y) < d)
d = min(d , p[rec[j]] - p[rec[i]]);
}
}
} double fenzhi(int l , int r)
{
int m = (l+r) >> ;
//这里是计算两点的最短距离,l==r只有一个点存在,所以输出一个最大距离使其不影响结果
if(l == r) return maxn;
if(l == r-) return p[l] - p[r]; double d;
//处理左边
double d1 = fenzhi(l , m);
//处理右边
double d2 = fenzhi(m+ , r);
//得到左右两部分中两点间的最小值
d = min(d1 , d2); //将这个最小值和左右两部分的点相连得到的最小边作比较
merge_l_r(d , l , r); return d;
} int main()
{
int n;
while(scanf("%d" , &n) , n){
for(int i = ; i<n ; i++){
scanf("%lf%lf" , &p[i].x , &p[i].y);
}
sort(p , p+n , cmpxy);
//这里是取圆的半径所以除以二
printf("%.2f\n" , fenzhi( , n-) / );
}
return ;
}

  

最新文章

  1. Xcode7中,如何新建category分类
  2. Centos7 mysql-community-5.7.11编译安装
  3. iOS - OC NSProcessInfo 系统进程信息
  4. JQuery与DOM中的区别
  5. SoapUI test WCF
  6. 如何关闭log4j中配置的spring或者hibernate的日志信息
  7. html+javascript实现可拖动可提交的弹出层对话框效果
  8. Xposed快速hook关键点
  9. (十七)java冒泡排序和compareto
  10. JSP:getOutputStream() has already been called for this response
  11. ThinkPhp框架对“数据库”的基本操作
  12. Confluence 6 编辑自定义 Decorators
  13. maven依赖查找方法
  14. 分库分表之后全局id怎么生成
  15. orz gzy
  16. 在 iOS 中信任手动安装的证书描述文件
  17. unigui结合JS方法记录
  18. 可以设置超时版的的fetch
  19. 《精通Python网络爬虫》
  20. html中,纯数字或纯英文的一串字符超出父容器不会折行显示,如何解决?

热门文章

  1. poj 2409 Let it Bead【polya定理+burnside引理】
  2. SpringCloud(Finchley版本)中Zull过滤器ResponseBoby返回中文乱码解决方案
  3. 使用frp工具实现内网的穿透以及配置多个ssh和web服务
  4. 【计蒜客习题】两仪剑法(gcd)
  5. 6.12---前提两个对象的成员必须一致,才能将有数据的对象将数据传给反射获取的对象conver(有数据对象,目标对象)
  6. CF816B Karen and Coffee
  7. 2017-12-04HTML布局_div布局
  8. Json--&gt;Newton.Json.dll的使用方法
  9. Android学习笔记(五)Android框架
  10. Java学习3_一些基础3_16.5.7