原 初学算法-分治法求平面上最近点对(Cl

    本来这个算法在笔者电脑里无人问津过一段时间了,但今天正好做HDU 1007见到了这个问题,今天就来把代码分享出来吧!

    我们首先将所有点按照坐标x排序一下,再做一条直线l当作“分割线”,方便我们递归。

    然后,我们就可以把这些点按照x轴的坐标分为左半部分和右半部分。那么最短距离一定在左半部分、右半部分、跨越左右的点对中的一个。 

    那么你可能会有疑问了:本来最近点对也一定在这三个区域内,这不还是相当于什么都没干吗?

    还真不是。我们可以假设通过递归得到了左边最小距离为d1,右边最小距离为d2,令δ = min(d1,d2)

    如图所示,如果跨越左右的点对可能是最短距离,那么它也必然比δ小。而在以l为中心、最大距离为2δ的区域中,最多有O(n)个如图所示的矩形。另外,可以证明对于每个矩形区域,最多尝试8个点对一定能找到最短距离(算法导论第33.4节有详细的证明,这里不再赘述)。

    因此,我们可以写出递归式:T(n)=2T(n/2)+O(n),可以用主项定理(master method)解得时间复杂度T(n)=O(nlogn)。加上排序一次的时间O(nlogn),因此整个算法的运行时间T(n)' = T(n)+O(nlogn) = O(nlogn)。

    下面,通过这个算法,我们就可以写出一份代码来:

/**
 * Find closest distance in N points.
 * Time cost: O(nlogn)
 * Author: Zheng Chen / Arclabs001
 * Copyright 2015 Xi'an University of Posts & Telecommunications
 */

/**
 * Algorithm:
 * First of all, sort the points in ascending order by x.
 * Divide the array into 2 parts, and find the smallest distance within two parts.
 * Let min as the smaller one, and find the smallest split distance.
 */
#include <iostream>
#include <algorithm>
#include <cmath>
#define INF 0x6FFFFFFF
using namespace std;

struct Node{
	double x, y;

	friend bool operator < (const Node &a, const Node &b){
		if(a.x == b.x)
			return a.y < b.y;
		return a.x < b.x;
	}
};

Node* Point = NULL;
/**
 * Calculate the distance between two points.
 * @return   [double, the distance between a and b]
 */
double _distance(const Node a, const Node b)
{
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double smaller(double p, double q)
{
	return (p > q) ? q : p;
}
/**
 * [Find the closest distance, divide & conquer]
 * @param  left  [search from where]
 * @param  right [to where]
 * @return       [double, the smallest distance in the whole set of points]
 */
double Closest_distance(int left, int right)
{
	double d = INF;
	double distance_tmp;

	if(left == right)
		return 0;
	if(right == left+1)
		return _distance( Point[left], Point[right] );
	int mid = (left + right) / 2;

	d = smaller( Closest_distance(left,mid) , Closest_distance(mid,right) );

	for(int i=mid-1; i>=left && Point[mid].x - Point[i].x < d; i--){
		for(int j = mid+1; j<=right && Point[j].x - Point[mid].x < d && fabs( Point[i].y - Point[j].y) < d; j++){
			distance_tmp = _distance( Point[i], Point[j] );
			if(distance_tmp < d)
				d = distance_tmp;
		}
	}

	return d;
}

int main()
{
    int n;
    cin>>n;
    Point = new Node[n];
    for(int i=0; i<n ; i++){
    	cin>>Point[i].x>>Point[i].y;
    }
    sort(Point,Point+n);
    cout<<Closest_distance(0,n-1)<<endl;
    return 0;
}

当然,直接套用这个代码提交到HDOJ会导致Exceed Time Limit,你懂的^_^

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

355100
来自专栏数据结构与算法

7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 两个正整数的最大公约数是G,最小公倍数是...

47480
来自专栏TensorFlow从0到N

TensorFlow从0到1 - 2 - TensorFlow核心编程

上一篇Hello, TensorFlow!中的代码还未解释,本篇介绍TensorFlow核心编程的几个基本概念后,那些Python代码就很容易理解了。 与Te...

484100
来自专栏小樱的经验随笔

1082 与7无关的数(思维题,巨坑)

1082 与7无关的数 题目来源:                 有道难题 基准时间限制:1 秒 空间限制:131072 KB 分值: 5        ...

34670
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

26760
来自专栏Spark学习技巧

CountVectorizer

CountVectorizer 关于文本特征提取,前面一篇文章TF-IDF介绍了HashingTF,本文将再介绍一种Spark MLlib的API CountV...

67670
来自专栏小樱的经验随笔

Gym 100952C&&2015 HIAST Collegiate Programming Contest C. Palindrome Again !!【字符串,模拟】

C. Palindrome Again !! time limit per test:1 second memory limit per test:64 meg...

26930
来自专栏C语言及其他语言

【每日一题】1426: [蓝桥杯][历届试题]九宫重排

如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面...

12130
来自专栏蜉蝣禅修之道

关于Havel算法判断度数序列能否构成简单图的思考

19120
来自专栏人工智能LeadAI

TensorFlow从0到1丨第2篇:TensorFlow核心编程

上一篇Hello, TensorFlow!中的代码还未解释,本篇介绍TensorFlow核心编程的几个基本概念后,那些Python代码就很容易理解了。 与Ten...

41040

扫码关注云+社区

领取腾讯云代金券