?

最近點對模板題，算法導論P591有具體的證明，我不會實現? - -！，有一個博主寫的很好，具體的證明可以見博客：http://blog.csdn.net/zhang20072844/article/details/6776386

#include?<iostream>
#include?<cstdio>
#include?<cstdlib>
#include?<cstring>
#include?<cmath>
#include?<algorithm>
using?namespace?std;
#define?MAXN?100010

struct?node
{
????double?x,?y;
}p[MAXN*2],?ym[MAXN*2];

int?n;

int?cmpx(const?node?a,?const?node?b)
{
????return?a.x?<?b.x;
}

int?cmpy(const?node?a,?const?node?b)
{
????return?a.y?<?b.y;
}

double?dist(node?a,?node?b)
{
????return?sqrt((a.x-b.x)*(a.x-b.x)?+?(a.y-b.y)*(a.y-b.y));
}

double?getmind(node?*p,?int?l,?int?r)
{
????if(l?==?r)?return?1e50;??????//只有一個點?
????if(l+1?==?r)?return?dist(p[l],?p[r]);?//只有兩個點?
????int?mid?=?(l+r)/2;
????double?ans?=?min(getmind(p,?l,mid),?getmind(p,?mid+1,?r));??//注意是getmind(p,?l,?mid);?
????int?yn?=?0;
????for(int?i?=?l;?i?<=?r?;?i++)???//divide
????{
????????if(fabs(p[i].x?-?p[mid].x)?<=?ans)
????????{
????????????ym[yn++]?=?p[i];
????????}
????}
????sort(ym,?ym+yn,?cmpy);?//預排序?
????for(int?i?=?0;?i?<?yn;?i++)
????{
????????for(int?j?=?i+1;?j?<?yn;?j++)
????????{
????????????if(ym[j].y?-?ym[i].y?>=?ans)?break;??//if(|y1-y2|?>=?ans)?break;
????????????ans?=?min(ans,?dist(ym[i],?ym[j]));
????????}
????}
????return?ans;
}


int?main()
{
????int?T;
????while(scanf("%d",?&n)?&&?n)
????{
????????for(int?i?=?0;?i?<?n;?i++)
????????{
????????????scanf("%lf%lf",?&p[i].x,?&p[i].y);
????????}
????????sort(p,?p+n,?cmpx);
????????double?ans?=?getmind(p,?0,?n-1);
????????if(ans?<=?10000)
????????{
????????????printf("%.4lf\n",?ans);
????????}
????????else?printf("INFINITY\n");
????}
????return?0;
}

?

轉載于:https://www.cnblogs.com/g0feng/archive/2012/10/18/2730193.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的UVA 10245 The Closest Pair Problem的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。