最近点对距离计算问题

Question

此题来自hduacm网站１００７题，http://acm.hdu.edu.cn/showproblem.php?pid=1007，提交结果是ＲＥ，题目中的几个例子输入，运行结果都正确，但输入有些数据，程序就卡主没法运行了，不知道代码错哪了！
下面是代码：
#include
#include
#include
#defineM1000
usingnamespacestd;
voidsorted(double**,int);//对点的X轴系数进行排序
doubleget_min(double,double);
doublecal_radius(double**,int,int);//计算圆环的最大半径
intmain()
{
intN[M],n;
double**pos;
doubleradius[M];
inti=1;
while(1)
{
cin>>N[i];
if(N[i]==0)break;
if(N[i]<2||N[i]>100000)return0;
pos=newdouble*[N[i]];
for(n=0;n{
pos[n]=newdouble[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(intj=1;j{
if(radius[j]==0)
cout<<"0.00"<else
{
cout.precision(2);
cout<}
}
return0;
}
voidsorted(double**pos,intn)//对点的X轴系数进行排序
{
inti,j;
doubletmp[2];
for(i=1;i{
if(pos[i][0]{
tmp[0]=pos[i][0];
tmp[1]=pos[i][1];
for(j=i-1;tmp[0]=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];
}
}
}
doubleget_min(doubled1,doubled2)
{
returnd1<=d2?d1:d2;
}
doublecal_radius(double**pos,intpre,inttail)//计算所有点之间的最小距离，并返回最小距离
{
intleft;//left表示在中界线左边的点的个数
intn=tail-pre+1;//二维数组长度
doublemid_line;//中界线
doubled1,d2,dmin,tmp_d;
double**tmp;
tmp=newdouble*[n];
if(n==2)
{
dmin=sqrt(pow(pos[pre][0]-pos[tail][0],2)+pow(pos[pre][1]-pos[tail][1],2));
returndmin;
}
if(n==3)
{
doublet1,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);
returndmin;
}
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(inti=n/2+pre,j=0;pos[i][0]>(mid_line-dmin);i--,j++)
{
tmp[j]=newdouble[2];
tmp[j][0]=pos[i][0];
tmp[j][1]=pos[i][1];
}
left=j;
left--;
for(intk=n/2+pre+1;pos[k][0]<(mid_line+dmin);k++,j++)
{
tmp[j]=newdouble[2];
tmp[j][0]=pos[k][0];
tmp[j][1]=pos[k][1];
}
j--;
for(inth=0;h{
for(j-=1;j>=left;j--)
{
if(tmp[j][1]-tmp[h][1]>-dmin&&tmp[j][1]-tmp[h][1]{
tmp_d=sqrt(pow(tmp[j][0]-tmp[h][0],2)+pow(tmp[j][1]-tmp[h][1],2));
if(tmp_ddmin=tmp_d;
}
}
}
delete[]tmp;//释放内存
returndmin;
}

Answer 1

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