最近点对问题 HDU Quoit Design 1007 分治法

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
#include<string>
#include<queue>
using namespace std;
const int maxn = ;
const long long INF = 0xfffffff;
struct Point
{
double x, y;
}P[maxn], Temp[maxn];
bool cmp(Point a, Point b)
{
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
bool cmpy(Point a, Point b)
{
return a.y < b.y;
}
double dis(Point a, Point b)
{
return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}
double Colosest(int L,int R)
{
if(L == R)
return INF;
if(L + == R)
return dis(P[L],P[R]);
int Mid = (L + R) / ;
double d1 = Colosest(L, Mid);
double d2 = Colosest(Mid + , R);
double d = min(d1, d2);
//递归找左右两侧的点,最小距离
int k = ; for(int i = Mid; i >= L; i--)
{
if( P[Mid].x - P[i].x < d )
Temp[k++] = P[i];
else
break;
} for(int j = Mid + ; j <= R; j++)
{
if(P[j].x - P[Mid].x < d)
Temp[k++] = P[j];
else
break;
}
//找出在中间点的可能点对 然后排序
sort(Temp,Temp+k,cmpy); for(int i=; i<k; i++)
{
/*需要一个 Temp[j].y - Temp[i].y < d 优化, 不然会超时*/
for(int j=i+; j < k && Temp[j].y - Temp[i].y < d ; j++)
{
double d3 = dis(Temp[j], Temp[i]);
if(d3 < d)
d = d3;
}
}
return d;
}
int main()
{
int n;
while(scanf("%d",&n) ,n)
{
for(int i=; i<n; i++)
scanf("%lf%lf",&P[i].x,&P[i].y);
sort(P,P+n,cmp);//先排序
printf("%.2lf\n", Colosest(,n-)/ );
}
return ;
}
上一篇:关于C#chart图表实现多条折线动态绑定数据的问题


下一篇:LoadRunner Controller: 压力机