POJ Raid 3714（最近点对）分治算法

题目描述

原题链接

After successive failures in the battles against the Union, the Empire retreated to its last stronghold. Depending on its powerful defense system, the Empire repelled the six waves of Union’s attack. After several sleepless nights of thinking, Arthur, General of the Union, noticed that the only weakness of the defense system was its energy supply. The system was charged by N nuclear power stations and breaking down any of them would disable the system.

The general soon started a raid to the stations by N special agents who were paradroped into the stronghold. Unfortunately they failed to land at the expected positions due to the attack by the Empire Air Force. As an experienced general, Arthur soon realized that he needed to rearrange the plan. The first thing he wants to know now is that which agent is the nearest to any power station. Could you, the chief officer, help the general to calculate the minimum distance between an agent and a station?

算法分析

分治算法，先按输入将所有点，用两个类型标记，再将所有点按x排序，以横坐标大小分成两组，再将每一半的点继续分成两半，递归分别求得两个部分的最近距离。求出mi=min{distance(p1,p2),distance(q1,q2)},在临界区，即两个区域之间找到距离小于mi的点对（pl,qr）。对于此时的点P，我们只需要找到在p的右邻域内最多6个点q，比较distance(p,q)与mi的大小，如果distance(p,q)<mi,则mi=distance(p,q),返回mi。

代码

#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;

struct node
{
	double x, y;
	int group;
};
node a[200000];
node p[100000], q[100000];

bool cmp(node a, node b)
{
	return a.x < b.x;
}
double distance(node a, node b)
{
	if (a.group != b.group)
		return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	else
		return 0x3f3f3f3f;
}
double minimumlen(int l, int r)
{
	if (l == r)
		return 0x3f3f3f3f;
	if (l == r - 1)
		return distance(a[l], a[r]);
	int mid = (l + r) / 2;
	double tmp1 = minimumlen(l, mid);
	double tmp2 = minimumlen(mid + 1, r);
	double mi = min(tmp1, tmp2);
	int t1 = 0, t2 = 0;
	for (int i = mid; i >= l; i--)
	{
		if ((a[mid].x - a[i].x) < mi)
			p[t1++] = a[i];
	}
	for (int i = mid + 1; i <= r; i++)
	{
		if ((a[i].x - a[mid].x) < mi)
			q[t2++] = a[i];
	}
	for (int i = 0; i < t1; i++)
	{
		for (int j = 0; j < t2; j++)
			mi = min(mi, distance(p[i], q[j]));
	}
	return mi;
}

int main()
{
	int testnum, n;
	cin >> testnum;
	while (testnum--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			cin >> a[i].x >> a[i].y;
			a[i].group = 1;
		}
		for (int i = n; i < 2 * n; i++)
		{
			cin >> a[i].x >> a[i].y;
			a[i].group = 2;
		}
		sort(a, a + 2 * n, cmp);
		cout << minimumlen(0, 2 * n - 1);
	}
	return 0;
}