nbhkdz.com冰点文库

最近点对


#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
const int maxn=100001;
struct atp{double x,y;};
int n;
at

p a[maxn],tmp[maxn];
void init()//读入
{ int i;
for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
}
void qsortx(int l,int r)//快排
{ int i,j;
double x;
atp t;
i=l;j=r;
x=a[(l+r)/2].x;
while(i<=j)
{
while(a[i].x<x)i++;
while(a[j].x>x)j--;
if(i<=j) { t=a[i];a[i]=a[j];a[j]=t; i++;j--;}
}
if(i<r)qsortx(i,r);
if(l<j)qsortx(l,j);
}
void qsorty(int l,int r)//快排
{ int i,j;
double x;
atp t;
i=l;j=r;
x=tmp[(l+r)/2].y;
while(i<=j)
{
while(tmp[i].y>x)i++;
while(tmp[j].y<x)j--;
if(i<=j)
{ t=tmp[i];tmp[i]=tmp[j];tmp[j]=t; i++;j--;}
}
if(i<r)qsorty(i,r);
if(l<j)qsorty(l,j);
}
double find(int l,int r)
- 13 -
{ int i,j,midd,tot;
double t,minn,xit;
if(l+1==r)//只有两个点时特殊处理
return sqrt((a[l].x-a[r].x)*(a[l].x-a[r].x)+(a[l].y-a[r].y)*(a[l].y-a[r].y));
if(l+2==r)//只有三个点时特殊处理
{ minn=100000000;
for(i=l;i<=r-1;i++)
for(j=i+1;j<=r;j++)
{ t=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
if(t<minn)minn=t;
}
return minn;
}
midd=(l+r)/2;
xit=(a[midd].x+a[midd+1].x)/2; //否则二分
minn=find(l,midd);
t=find(midd+1,r);
if(t<minn)minn=t; //更新minn
tot=0;
for(i=l;i<=r;i++)//记录在矩形内的点
if(abs(a[i].x-xit)<minn)
{ tot++;
tmp[tot].x=a[i].x;
tmp[tot].y=a[i].y;
}
if(tot>1)qsorty(1,tot); //以Y 坐标为关键字从大到小排序
for(i=1;i<=tot-1;i++)//求i 点和下面7 个点的距离
for(j=i+1;j<=i+7;j++)
{
if(j>tot)break;
t=sqrt((tmp[i].x-tmp[j].x)*(tmp[i].x-tmp[j].x)+
(tmp[i].y-tmp[j].y)*(tmp[i].y-tmp[j].y));
if(t<minn)minn=t;
}
return minn;
} int main()
{ cin>>n;
init();
qsortx(1,n); //以X 坐标为关键字从小到达排序
cout<<fixed<<setprecision(2)<<find(1,n)<<endl;
return 0;
}

求最近点对算法

《算法设计与分析》上机报告姓名: 上机题目: 学号: 日期: 求最近点对算法 实验环境: CPU: 2.10GHz ; 内存: 6G ; 操作系统:Win7 64 位 ;软件平台:Visual...

最近点对分治法

[i++]); } 他的算法是有问题的: 假设点是 (-5,2) ,(-3, -2) ,(-0.5, -100)和点(0,1)得到的最近点对距离是 4.47 所以我就没有点的纵坐标...

算法设计与实验分析二:最近点对问题

算法设计与实验分析二:最近点对问题 班级:网络 1101 姓名:齐岳川 学号:1111610210 日期:2013.4.9 一:实验名称:最近点对问题 二:实验内容: 使用递归算法求解平面...

最近点对问题

最近点对问题_互联网_IT/计算机_专业资料。分治法,最近点对问题算法分析与设计 最近对问题 最近对问题问题描述: 在二维平面上的 n 个点中,如何快速的找出最近的...

最近点对问题

最近点对问题_IT/计算机_专业资料。最近点对问题 I.一维问题: 一维问题: 一维问题 一、问题描述和分析 最近点对问题的提法是:给定平面上 n 个点,找其中的一...

算法实验四_空间最近点对算法

算法实验四_空间最近点对算法_计算机软件及应用_IT/计算机_专业资料。算法实验 空间最近点对一、算法分析该算法的问题描述为:给定二维平面上的点集,求解距离最近的...

求最近点对的随机算法

最近点对的随机算法_研究生入学考试_高等教育_教育专区。算法课件 研究生入学考试求最近点对的随机算法 分治法求解需 O(nlogn)时间, 而用随机算法求解可达到 O...

分治法解最接近点对问题

1) 算法分析 问题描述:已知集合 S 中有 n 个点,求这些点中最近的两个点的距离 算法分析: 分治法的思想就是将 S 进行拆分,分为 2 部分求最近点对。将 S...

最接近点对问题实验报告

最接近点对问题实验报告_IT/计算机_专业资料。最接近点对问题一.实验目的: 1....由于距离最近 的两个点可能在不同的区域中,需要进一步判断。 选择 S1 中的一...

实验七 最近点对问题的设计与实现

实验七一、 实验目的 1.掌握分治算法的基本原理 最近点对问题的设计与实现 2.利用分治策略编程解决最近点对问题 二、 实验要求 1.设计算法 2.写出相应程序 3....