问题描述:

源码:

经典问题——最近邻问题,标准解法

#include"iostream"
#include"algorithm"
#include"cmath"
using namespace std; struct Point
{
double x;
double y;
}; Point S[100000];//不使用全局变量可能会超内存 bool cmpPointX(Point a, Point b)
{
return a.x > b.x;
} bool cmpPointY(Point a, Point b)
{
return a.y > b.y;
} double EfficientClosestPair(Point *P, Point *Q, int start, int n)
{
if(n <= 3)
{
double result;
result = (P[start].x - P[start+1].x)*(P[start].x - P[start+1].x) + (P[start].y - P[start+1].y) * (P[start].y - P[start+1].y);
if(n == 3)
{
double tmp = (P[start].x - P[start+2].x)*(P[start].x - P[start+2].x) + (P[start].y - P[start+2].y) * (P[start].y - P[start+2].y);
if(tmp < result)result = tmp;
tmp = (P[start+1].x - P[start+2].x)*(P[start+1].x - P[start+2].x) + (P[start+1].y - P[start+2].y) * (P[start+1].y - P[start+2].y);
if(tmp < result)result = tmp;
}
return result;
}
else
{
int half = n / 2;
double d1 = EfficientClosestPair(P, Q, start, half);
double d2 = EfficientClosestPair(P, Q, start + half, n - half);
double d = d1 < d2 ? d1 : d2;
double m = P[start + half - 1].x;
int count = 0;
double tmp;
for(int i = start; i < start + n; i++)
{
tmp = Q[i].x - m;
if(tmp < 0)tmp = - tmp;
if(tmp < d)count++;
}
double dminsq = d;
if(count > 1)
{
//Point *S = new Point[count];
for(int i = start, j = 0; i < start + n; i++)
{
tmp = Q[i].x - m;
if(tmp < 0)tmp = - tmp;
if(tmp < d)
{
S[j].x = Q[i].x;
S[j].y = Q[i].y;
j++;
}
}
int k;
for(int i = 0; i < count - 1; i++)
{
k = i + 1;
while(k < count && (S[k].y - S[i].y)*(S[k].y - S[i].y) < dminsq)
{
dminsq = min((S[k].x - S[i].x)*(S[k].x - S[i].x) + (S[k].y - S[i].y)*(S[k].y - S[i].y), dminsq);
k++;
}
}
} return dminsq; }
} int main()
{
int n;
Point *P, *Q;
cout.precision(2);
cout.setf(ios::fixed);
P = new Point[100000];
Q = new Point[100000];
while(scanf("%d", &n) != EOF)
{
if(n == 0)break;
for(int i = 0; i < n; i++)
{
scanf("%lf %lf", &P[i].x,&P[i].y);
Q[i].x = P[i].x;
Q[i].y = P[i].y;
}
if(n <= 3)
{
cout<<sqrt(EfficientClosestPair(P, Q, 0, n)) / 2<<endl;
}
else
{
sort(P, P+n, cmpPointX);//使用qsort可能会超时
sort(Q, Q+n, cmpPointY);
cout<<sqrt(EfficientClosestPair(P, Q, 0, n)) / 2<<endl;
}
}
return 0;
}

  

最新文章

  1. Resources.Load加载文件返回null的原因
  2. [LeetCode] Design Hit Counter 设计点击计数器
  3. 1、CC2541蓝牙4.0芯片中级教程——基于OSAL操作系统的运行流程了解+定时器和串口例程了解
  4. hdu 2037 - 今年暑假不AC(区间调度问题)
  5. Java-EnumSet
  6. kindeditor html代码过滤不能保存
  7. org.hibernate.HibernateException: could not instantiate RegionFactory [org.hibernate.cache.impl.bridge.RegionFactoryCacheProviderBridge]
  8. Learning WCF Chapter2 Service Contracts
  9. C++对象模型学习笔记
  10. gem安装时出现 undefined method `size&#39; for nil:NilClass (NoMethodError) 的解决办法
  11. (转)IOS笔记 #pragma mark的用法
  12. Handler和HandlerThread
  13. for循环执行步骤
  14. Android获取状态栏高度、标题栏高度、编辑区域高度
  15. 【转】百度站长平台MIP引入工具使用心得
  16. Android-Java-抽象类
  17. .net 事务处理
  18. View动画(补间动画)
  19. 【javascript】获取 格式化时间
  20. out, ref 和 params 的区别和用法

热门文章

  1. tomcat注册windows服务
  2. 7 Python+Selenium浏览器设置
  3. 给html里面的class添加一个判断语句,判断当前class是否显示(vue)
  4. jQuery 插入元素
  5. day09网络编程
  6. 2104 -- K-th Number
  7. Javascript中的原型链,__proto__和prototype等问题总结
  8. nyoj11-奇偶数分离
  9. BZOJ 3434 [WC2014]时空穿梭 (莫比乌斯反演)
  10. Centos上Mysql5.6的安装