本文主要是介绍POJ 3714 Raid 最近点对，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求最近点对，只不过这两个点需要属于不同的集合，那么就给两个集合的点分别标记一个id号，在计算时，两个集合合并起来，并排序，递归求解，只不过，求两点距离时，如果id号是同一集合的，直接返回一个很大的数就行了，这样就跟求一个集合的最近点对没什么区别了。
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 2000000000
#define LOCA
using namespace std;
struct node
{double x;double y;int id;
}p[200005],p1[100005],p2[100005];
bool cmp(node x, node y)
{return x.x < y.x;
}
double dist(node x, node y)
{if(x.id != y.id)return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));else return 2100000000.0; // id号相同肯定不行，直接返回一个很大的数
}
double Divide_conquer(int low, int high)
{if(high == low) return 2100000000.0; if(high - low == 1) return dist(p[low], p[high]);int mid = (low + high) / 2;double d1 = Divide_conquer(low, mid);double d2 = Divide_conquer(mid + 1, high);double d = min(d1, d2);int i, j, cnt1 = 0, cnt2 = 0;for(i = mid; i >= low; i--){if(p[mid].x - p[i].x < d){p1[cnt1++] = p[i];}}for(i = mid + 1; i <= high; i++){if(p[i].x - p[mid].x < d){p2[cnt2++] = p[i];}}for(i = 0; i < cnt1; i++){for(j = 0; j < cnt2; j++){d = min(d, dist(p1[i], p2[j]));}}return d;
}
int main()
{
#ifdef LOCALfreopen("calfflac.in","r",stdin);freopen("calfflac.out","w",stdout);
#endifint t, n, i, j;scanf("%d", &t);while(t--){scanf("%d", &n);for(i = 0; i < n; i++){scanf("%lf%lf", &p[i].x, &p[i].y);p[i].id = 1;}for(i = n; i < 2 * n; i++){scanf("%lf%lf", &p[i].x, &p[i].y);p[i].id = 2;}n = n * 2;sort(p, p + n, cmp);printf("%.3f\n", Divide_conquer(0, n - 1));}return 0;
}
这篇关于POJ 3714 Raid 最近点对的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
