The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

HDOJ 1007 Quoit Design 平面最近点对

刚好课上学了平面最近点对的算法,回来实现以下,恩 ,分治的思想很重要。呵呵,又学会了一个算法。

#include<iostream>
#include
<cstdio>
#include
<cmath>
#include
<algorithm>
using namespace std;
#define eps 1e-8

const int maxn=200001;
const double INF=999999999;

typedef 
struct point
{
    
double x,y;
    
//int flag;
    point(){};  
}
point;
point p[maxn];
int n; 
int cmp(double x,double y)
{
    
if(x==y)return 0;
    
if(x>y)return 1;
    
return -1
}
       

bool cmp1(point a,point b)
{
    
if(a.x!=b.x)
        
return a.x<b.x;
    
else
        
return a.y<b.y;
}

bool cmp2(int i,int j)
{
    
return cmp(p[i].y,p[j].y)<0;
}

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



int y[maxn],len;
double cp(point p[],int l,int r)//求从l到r这些点的最近点对
{
    
int i,j;
    
int mid=(l+r)>>1;
    
double ret=INF;
    
if(l>=r)
        
return ret;
    
for(i=mid;i>=l&&!cmp(p[i].x,p[mid].x);i--);
    
double t1=cp(p,l,i);
    
for(i=mid;i<=r&&!cmp(p[i].x,p[mid].x);i++);
    
double t2=cp(p,i,r);
    
if(t1<t2)
        ret
=t1;
    
else ret=t2;

    len
=0;
    
for(i=l;i<=r;i++)
    
{
        
if(fabs(p[i].x-p[mid].x)<ret)
            y[
++len]=i;
    }


    sort(y
+1,y+len+1,cmp2);

    
for(i=1;i<=len;i++)
    
{
        
int cnt=1;
        
for(j=i+1;j<=len&&cnt<=7;j++)
        
{
            ret
=min(ret,dist(p[y[i]],p[y[j]])); 
            cnt
++;
        }

    }

    
return ret;
}


bool check(int n)
{
    
int i;
    
for(i=2;i<=n;i++)
    
{
        
if(p[i].x==p[i-1].x&&p[i].y==p[i-1].y)
            
return true;
    }

    
return false;
}




int main()
{

    
int n;
    
while(scanf("%d",&n)!=EOF)
    
{    
        
if(n==0)
            
break;

        
int i;
        
for(i=1;i<=n;i++)
            scanf(
"%lf%lf",&p[i].x,&p[i].y);
        sort(p
+1,p+n+1,cmp1);
        
if(check(n))
        
{
            printf(
"0.00\n");
            
continue;
        }

        
double ans=cp(p,1,n)/2;
        printf(
"%.2lf\n",ans);

    }

    
return 0;    

}












 

posted on 2010-05-20 20:13 abilitytao 阅读(2207) 评论(4)  编辑 收藏 引用

评论

# re: HDOJ 1007 Quoit Design 平面最近点对 2010-05-21 00:43 矩阵操作

遍历比较距离时你根本就不需要进行开平方这个多余的耗时操作
哎。。。
  回复  更多评论   

# re: HDOJ 1007 Quoit Design 平面最近点对[未登录] 2010-05-21 01:17 abilitytao

@矩阵操作
有道理 :-) 多谢提醒  回复  更多评论   

# re: HDOJ 1007 Quoit Design 平面最近点对 2010-05-21 17:54 <A href="mailto:wolf5x1016@gmail.com"

delaunay triangualtion  回复  更多评论   

# re: HDOJ 1007 Quoit Design 平面最近点对[未登录] 2010-05-21 19:02 abilitytao

@&lt;A href=&quot;mailto:wolf5x1016@gmail.com&quot;
网页爬虫?  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理