求最近点对,只不过这两个点需要属于不同的集合,那么就给两个集合的点分别标记一个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 LOCAL
freopen("calfflac.in","r",stdin);
freopen("calfflac.out","w",stdout);
#endif
int 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;
}
分享到:
相关推荐
三道几何题:hdu 1007、hdu 2289、poj 3714
POJ 最接近点对问题 ACM北大 using namespace std; struct Point { float x; float y; };
POJ 2659 Raid 分治法解决两组点中距离最近的点对
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2002-Squares 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
poj 1001答案