最近点对HDU1007

利用二分的方法来计算,应该是说利用分治的方法吧! 刚开始感觉时间会爆 后来发现嘎嘎居然没有 ,嗨自己算错了时间:

#include <iostream>

#include<cstdio>

#include<string.h>

#include<algorithm>

#include<cmath>

using namespace std;

struct point

{

    double x,y;

    point (double a=0,double b=0)

    {

        x=a;y=b;

    }

};

struct point p[100005];

int  a[100005];

bool cmp1(point a,point b)

{

    if(a.x<b.x)return true;

    else return false;

}

bool cmp2(int a,int b)

{

    if(p[a].y<p[b].y)return true;

    else return false ;

}

double dist(point a,point b)

{

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double min_value(double a,double b){ return a>b?b:a;}

double find(int l,int r)

{

    if(l+1==r) return dist(p[l],p[r]);

    if(l+2==r)

	{

		double a1=dist(p[l],p[l+1]);

		double a2=dist(p[l+1],p[r]);

		double a3=dist(p[l],p[r]);

		a1= min_value(a1,min_value(a2,a3));

        return a1;

	}

	int mid,i,num,j;

    double ans;

    mid=(l+r)/2;

    num=0;

    ans=min_value(find(l,mid),find(mid+1,r));

    for(i=l;i<=r;i++)

        if(p[i].x>=p[mid].x-ans&&p[i].x<=p[mid].x+ans)

        a[num++]=i;

        sort(a,a+num,cmp2);

        for(i=0;i<num;i++)

        for(j=i+1;j<num;j++)

        {

            if(p[a[j]].y-p[a[i]].y>ans)break;

            ans=min_value(ans,dist(p[a[j]],p[a[i]]));

        }

        return ans;

}

int main()

{

    double x,y;

    int n,i;

    while(scanf("%d",&n)==1)

    {

        if(n==0)break;

        for(i=0;i<n;i++)

       {

           scanf("%lf%lf",&x,&y);

           p[i]=point(x,y);

       }

       sort(p,p+n,cmp1);

     printf("%.2lf\n",find(0,n-1)/2);

    }

    return 0;

}