c++ - 最近点对距离计算问题

Question

此题来自hdu acm网站１００７题，http://acm.hdu.edu.cn/showproblem.php?pid=1007，提交结果是ＲＥ，题目中的几个例子输入，运行结果都正确，但输入有些数据，程序就卡主没法运行了，不知道代码错哪了！
下面是代码：

#include<iostream>
#include<iomanip>
#include<cmath>

#define M 1000
using namespace std;
void sorted(double**,int); //对点的X轴系数进行排序
double get_min(double ,double ); 
double cal_radius(double** ,int ,int );  //计算圆环的最大半径

int main()
{
    int N[M],n;
    double** pos;
    double radius[M];
    int i=1;
    while(1)
    {
        cin>>N[i];
        if(N[i]==0) break;
        if(N[i]<2||N[i]>100000) return 0;
        pos=new double*[N[i]];
        for(n=0;n<N[i];n++)
        {
            pos[n]=new double[2];
            cin>>pos[n][0]>>pos[n][1];
        }
        sorted(pos,n);  //对x系数进行排序
        radius[i]=cal_radius(pos,0,n-1)/2.00;  //计算所有点之间的最小距离
        i++;
        delete []pos; //释放内存
    }
    for(int j=1;j<i;j++)
    {
        if(radius[j]==0)
            cout<<"0.00"<<endl;
        else
        {
            cout.precision(2);
            cout<<radius[j]<<endl;
        }
    }
    return 0;
}

void sorted(double** pos,int n)  //对点的X轴系数进行排序
{
    int i,j;
    double tmp[2];
    for(i=1;i<n;i++)
    {
        if(pos[i][0]<pos[i-1][0])
        {
            tmp[0]=pos[i][0];
            tmp[1]=pos[i][1];
            for(j=i-1;tmp[0]<pos[j][0]&&j>=0;j--)
            {
                pos[j+1][0]=pos[j][0];
                pos[j+1][1]=pos[j][1];
            }       
            pos[j+1][0]=tmp[0];
            pos[j+1][1]=tmp[1];
        }
    }
}

double get_min(double d1,double d2)
{
    return d1<=d2?d1:d2;
}

double cal_radius(double** pos,int pre,int tail)  //计算所有点之间的最小距离，并返回最小距离
{
    int left;  //left表示在中界线左边的点的个数
    int n=tail-pre+1; //二维数组长度
    double mid_line;  //中界线
    double d1,d2,dmin,tmp_d;  
    double** tmp;
    tmp=new double*[n];
    if(n==2)
    {
        dmin=sqrt(pow(pos[pre][0]-pos[tail][0],2)+pow(pos[pre][1]-pos[tail][1],2));
        return dmin;
    }
    if(n==3)
    {
        double t1,t2,t3;
        t1=sqrt(pow(pos[pre][0]-pos[pre+1][0],2)+pow(pos[pre][1]-pos[pre+1][1],2));
        t2=sqrt(pow(pos[pre][0]-pos[pre+2][0],2)+pow(pos[pre][1]-pos[pre+2][1],2));
        t3=sqrt(pow(pos[pre+1][0]-pos[pre+2][0],2)+pow(pos[pre+1][1]-pos[pre+2][1],2));
        dmin=get_min(get_min(t1,t2),t3);
        return dmin;
    }
    mid_line=pos[n/2+pre][0];
    if(n%2==0)
    {
        d1=cal_radius(pos,pre,n/2+pre-1);
        d2=cal_radius(pos,n/2+pre,tail);
    }
    else
    {
        d1=cal_radius(pos,pre,n/2+pre);
        d2=cal_radius(pos,n/2+pre+1,tail);
    }
    dmin=get_min(d1,d2);
    for(int i=n/2+pre,j=0;pos[i][0]>(mid_line-dmin);i--,j++)
    {
        tmp[j]=new double[2];
        tmp[j][0]=pos[i][0];
        tmp[j][1]=pos[i][1];
    }
    left=j;
    left--;
    for(int k=n/2+pre+1;pos[k][0]<(mid_line+dmin);k++,j++)
    {
        tmp[j]=new double[2];
        tmp[j][0]=pos[k][0];
        tmp[j][1]=pos[k][1];
    }
    j--;
    for(int h=0;h<left;h++)
    {
        for(j-=1;j>=left;j--)
        {
            if(tmp[j][1]-tmp[h][1]>-dmin&&tmp[j][1]-tmp[h][1]<dmin)
            {
                tmp_d=sqrt(pow(tmp[j][0]-tmp[h][0],2)+pow(tmp[j][1]-tmp[h][1],2));
                if(tmp_d<dmin)
                    dmin=tmp_d;
            }
        }
    }
    delete []tmp; //释放内存
    return dmin;
}

Answer 1

没有看你的代码，就个人做 ACM 的题，提一点建议：
1. 主函数不要太长，要处理好结构，把一些内容适当拆分成函数
2. 尽量避免动态内存。尤其是，你为什么丧心病狂的用了二维指针！
3. 不要指望别人会花时间看你写的长代码，尤其是你的代码描述性不强
4. 不要指望样例帮你 debug。学着自己生成测试数据
5. 不管你是搞OI/ACM，还是做做这类题锻炼思维，相信我，这将是你美妙的回忆

Answer 2

既然题主直接贴代码求解答。。。

那我也直接贴代码做为答案吧～～哈哈～～

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

#define print(x) cout<<x<<endl
#define input(x) cin>>x
#define SIZE 100010

const double eps=1e-8;
const double inf=1e100;

inline int zero(double x)
{
    if(x>eps) return 1;
    else if(x<-eps) return -1;
    else return 0;
}

struct point
{
    double x,y;
    point(){}
    point(double ix,double iy)
    {
        x=ix;y=iy;
    }
};

inline double mul(double x)
{
    return x*x;
}

inline double xmult(const point &sp,const point &ep,const point &op)
{
    return ((sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x));
}

inline double pntDis(const point &a,const point &b)
{
    return sqrt(mul(a.x-b.x)+mul(a.y-b.y));
}

bool cmpX(const point &a,const point &b)
{
    return a.x>b.x;
}

bool cmpY(const point &a,const point &b)
{
    return a.y<b.y;
}

point array[SIZE];
point ym[SIZE];

double minDisPointPair(int st,int end,point *ip)
{
    double res=inf;
    if(end-st<19)
    {
        for(int i=st;i<=end;i++)
        {
            for(int j=i+1;j<=end;j++)
            {
                res=min(res,pntDis(ip[i],ip[j]));
            }
        }
        return res;
    }
    else
    {
        int mid=(st+end)>>1;
        res=min(minDisPointPair(st,mid,ip),minDisPointPair(mid+1,end,ip));
        int yn=0;

        for(int i=st;i<=end;i++)
        {
            if(ip[i].x>=ip[mid].x-res && ip[i].x<=ip[mid].x+res) ym[yn++]=ip[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>=res) break;
                res=min(res,pntDis(ym[i],ym[j]));
            }
        }
        return res;
    }
}

int n;

int main()
{
    double a,b;
    while(input(n) && n)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&a,&b);
            array[i]=point(a,b);
        }
        sort(array,array+n,cmpX);
        printf("%.2lf\n",minDisPointPair(0,n-1,array)/2.0);
    }
}

Answer 3

个人建议lz自己调试。治愈卡在了哪里，lz可以在可能卡主的地方（附近）添加printf（打印上下文，或者只是标记都行）。这样lz就可以确定程序到底跑到哪里的时候出问题了。