2016级算法第六次上机-E.Bamboo之吃我一拳

Bamboo之吃我一拳

分析

当两个点的距离<=d时，才可以出拳，想要使得满足出拳条件的点对最少但不为0

寻找最近点对距离，得到的最近距离能够使得可以出拳的组数最少，因为除了最近点对外其他组合均不符合条件。

在一堆点中找到两个点的距离最小，暴力的O(n^2)计算量很恐怖，可以用分治思想把问题变小：
把平面上的点分为两拨，距离最近的两个点只可能出现在：第一堆，第二堆，和两堆2中各自一个点
分解
想象一条垂直线把所给点集分成两拨：所有的点要么在直线左边，要么在其右边。按x坐标升序排列。
解决
划分后两次递归调用，一次找到左边中的最近点对，一次找右边中的最近点对。取d'为两者中的最小值
合并
最近点对的距离d要么是某次递归找到的d'，要么是左边右边各取一个点组成的点对。就要查找是否存在距离小于d'且一个在左一个在右的点对。如果这两个点的距离<d'，那么两个点其实都各自在距离垂直线d'的距离之内。也就是以垂直线为轴线，宽度为2*d'的范围内，将这个范围内的点取出，并按照Y升序排列，只需要遍历任一点与范围内周围7个点的距离就可以了，比较选择更小值。

代码

#include <iostream>
#include <algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<iomanip>
using namespace std;

const int maxx = 1e5 + 3;
int num[maxx];
struct point{
	int x, y;
}p[maxx];
bool cmpx(const point&a, const point& b)//按x坐标排序
{
	return a.x<b.x;
}
bool cmpy(const int& a, const int &b)//按y坐标排序
{
	return p[a].y<p[b].y;
}
double dis(point a, point b)//计算两点距离
{
	return ((double)(a.x - b.x)*(a.x - b.x) + (double)(a.y - b.y)*(a.y - b.y));
}
double closest(int low, int high)//求最近距离
{
	if (low + 1 == high)//两个点情况，已经递归到底
		return dis(p[low], p[high]);
	if (low + 2 == high)//三个点
		return min(dis(p[low], p[high]), min(dis(p[low], p[low + 1]), dis(p[low + 1], p[high])));
	int mid = (low + high) / 2;
	double ans = min(closest(low, mid), closest(mid + 1, high));//两组分别递归，去最下者

	int i, j, cnt = 0;
	for (i = low; i <= high; i++)
	{
		if (p[i].x >= p[mid].x - ans && p[i].x <= p[mid].x + ans)
			num[cnt++] = i;
	}
	sort(num, num + cnt, cmpy);//这是在直线两侧ans距离内的点按y坐标排序
	for (i = 0; i < cnt; i++) {
		int k = i + 7 > cnt ? cnt : i + 7;
		for (j = i + 1; j < k; j++) {
			if (p[num[j]].y - p[num[i]].y > ans)
				break;
			ans = min(dis(p[num[i]], p[num[j]]), ans);
		}
	}
	return ans;
}
int main()
{
    int n;
	while (~scanf("%d", &n))
	{
		for (int i = 0; i<n; i++)
			scanf("%d %d", &p[i].x, &p[i].y);
		sort(p, p + n, cmpx);
		double ans = closest(0, n - 1);
		ans = sqrt(ans);
		printf("%.2lf
", ans);
	}
}

另外

严格的说本题的数据是要卡掉O(n^2)暴力算法的，但你们的grh大佬借助sin 和cos计算距离，运算时间甚至比O(nlogn)的分治法还要快，，，