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

I haven’t looked at your code, but I would like to give you some suggestions based on my personal ACM questions:
1. The main function should not be too long, the structure should be properly handled, and some content should be appropriately split into functions
2. Try to avoid dynamic memory. In particular, why did you use the two-dimensional pointer so crazily!
3. Don’t expect others to take the time to read the long code you write, especially if your code is not very descriptive
4. Don’t expect samples to help you debug. Learn to generate test data yourself
5. Whether you are doing OI/ACM or doing this kind of questions to exercise your thinking, believe me, this will be a wonderful memory for you

Answer 2

Since the questioner directly posted the code to ask for the answer. . .

Then I will post the code directly as the answer~~Haha~~

#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

I personally recommend lz to debug it by himself. To cure where the card is, lz can add printf (printing context, or just marking) where (nearby) the possible card owner is. In this way, lz can determine where the program went when something went wrong.