题目大意:
  平面最近点对。

思路:
  分治。
  首先将所有点排序
  每次把当前区间分为两半,递归求解两个区间内部的情况,然后枚举区间两边的点。

 #include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
typedef std::pair<double,double> Point;
const int N=;
Point p[N];
int num[N];
double ans=1e10;
inline double sqr(const double &x) {
return x*x;
}
inline double dis(const Point &a,const Point &b) {
return sqrt(sqr(std::abs(a.first-b.first))+sqr(std::abs(a.second-b.second)));
}
void solve(const int &l,const int &r) {
if(l==r) return;
const int mid=(l+r)/;
solve(l,mid);`
solve(mid+,r);
num[]=;
for(register int i=mid+;i<=r;i++) {
if(p[i].first-p[mid].first<ans) {
num[++num[]]=i;
}
}
for(register int i=l;i<=mid;i++) {
if(p[mid].first-p[i].first<ans) {
for(register int j=;j<=num[];j++) {
ans=std::min(ans,dis(p[i],p[num[j]]));
}
}
}
}
int main() {
const int n=getint();
for(register int i=;i<n;i++) {
scanf("%lf%lf",&p[i].first,&p[i].second);
}
std::sort(&p[],&p[n]);
solve(,n-);
printf("%.4f\n",ans);
return ;
}

最新文章

  1. JS和JSON的区别
  2. java多线程编程
  3. Page传回页面的值问题
  4. oracle索引使用时注意
  5. Delphi For Android 开发笔记-附:如何Delphi中同时实现Windows、Android版的GetModuleFileName函数
  6. 自动化运维——一键安装MySQL
  7. (原)配置vs2013使用intel的IPP库
  8. awk详解 数组
  9. Eclipse从数据库逆向生成Hibernate实体类和映射文件(Eclipse插件系列之HibernateTools)
  10. 大战Java虚拟机【3】—— 类加载机制
  11. post传递中文时,可以使用urlEncode编码进行转码
  12. Golang之发送消息至kafka
  13. IDEA与Eclipse
  14. vue2.0项目中 localhost改成ip地址访问
  15. PC/FORTH 循环
  16. Quart2D矩阵变换
  17. JDK5新特性之 可变参数的方法
  18. Istio全景监控与拓扑
  19. Hibernate中的Session缓存问题
  20. extjs [1]

热门文章

  1. virsh command
  2. java 中基本类型与字符串之间的互相转换
  3. 运维必须掌握的Linux面试题
  4. hdu 1172 猜数字
  5. 洛谷 P4882 lty loves 96! 解题报告
  6. spring in action 学习笔记六:bean在不同情况下的默认id号或者将名字
  7. java 复习整理(二 数据类型和几种变量)
  8. web本地存储 sessionStorage 和 localStorage
  9. Topcoder SRM 605 div1 题解
  10. WebApi初探之基本操作(CRUD)