题意:求平面最近点对之间的距离

解:首先可以想到枚举的方法,枚举i,枚举j算点i和点j之间的距离,时间复杂度O(n2).

  如果采用分治的思想,如果我们知道左半边点对答案d1,和右半边点的答案d2,如何求跨两边点之间的答案呢?显然只用枚举中线两边d=min(d1,d2)范围的点,并且每个点都只需要枚举上下范围在d以内的点,显然这样的点不会很多。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <map>
using namespace std;
typedef long long ll;
const double inf=1e20;
const int maxn=; struct Point{
double x, y;
}point[maxn]; int n, mpt[maxn]; //以x为基准排序
bool cmpxy(const Point &a,const Point &b){
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
} bool cmpy(const int &a,const int &b){
return point[a].y<point[b].y;
} double min(double a,double b){
return a<b?a:b;
} double dis(int i,int j){
return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y));
} double Closest_Pair(int left, int right){
double d=inf;
if(left==right)
return d;
if(left+==right)
return dis(left,right);
int mid=(left+right)>>;
double d1=Closest_Pair(left,mid);
double d2=Closest_Pair(mid+,right);
d=min(d1,d2);
int i,j,k=;
//分离出宽度为d的区间
for(i=left;i<=right;i++){
if(fabs(point[mid].x-point[i].x)<=d)
mpt[k++]=i;
}
sort(mpt,mpt+k,cmpy);
//线性扫描
for(i=;i<k;i++){
for(j=i+;j<k&&point[mpt[j]].y-point[mpt[i]].y<d; j++){
double d3=dis(mpt[i],mpt[j]);
if(d>d3)d=d3;
}
}
return d;
} int main(){
while(scanf("%d",&n)!=EOF){
if(n==)break;
for(int i=;i<n;i++)
scanf("%lf%lf",&point[i].x,&point[i].y);
sort(point,point+n,cmpxy);
printf("%.2lf\n",Closest_Pair(,n-)/);
}
return ;
}

最新文章

  1. 两个NOI题目的启迪8皇后和算24
  2. xcode 插件之KSImageNamed-Xcode
  3. [Hive - LanguageManual] Archiving for File Count Reduction
  4. C++ Primer Plus(第6版)中文版——课后练习程序代码
  5. JavaSE学习总结第19天_IO流1
  6. 看看微软代码的水平——Windows Live Writer 完成开源并推出开源分支
  7. 04-Foundation-NSSet、NSDictionary、block
  8. runloop和runtime
  9. Excel 一键上传到数据库
  10. Java的栈和队列
  11. [LeetCode] Number Complement 补数
  12. LCD接口和RGB介绍【转】
  13. C++智能指针剖析(上)std::auto_ptr与boost::scoped_ptr
  14. [python]Generators
  15. C++类型转换的注意事项
  16. opengl摄像机
  17. CentOS 下tomcat安装
  18. modprobe lsmod
  19. SSH 学习记录及在SSH模式下使用XShell连接服务器
  20. J2EE开发实战基础系列之开卷有益

热门文章

  1. Python原来这么好学-2.1节: 选择PyCharm作为开发工具
  2. Android Studio安装虚拟机步骤
  3. 多线程笔记 - provider-consumer
  4. 使用jquery封装的动画脚本(无动画、css3动画、js动画)
  5. Vue.js 从源码理解v-for和v-if的优先级的高低
  6. [红日安全]Web安全Day2 - XSS跨站实战攻防
  7. Apache Log4j 反序列化代码执行(CVE-2019-17571) 漏洞分析
  8. Android中ProgressBar的使用-通过Handler与Message实现进度条显示
  9. pip 自己的源 搭建
  10. POST注入之sqlmap