此题来自hdu acm网站1007题,http://acm.hdu.edu.cn/showproblem.php?pid=1007,提交结果是RE,题目中的几个例子输入,运行结果都正确,但输入有些数据,程序就卡主没法运行了,不知道代码错哪了!
下面是代码:
#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;
}
沒有看你的代碼,就個人做 ACM 的題,提一點建議:
1. 主函數不要太長,要處理好結構,把一些內容適當拆分成函數
2. 盡量避免動態內存。尤其是,你為什麼喪心病狂的用了二維指針!
3. 不要指望別人會花時間看你寫的長代碼,尤其是你的代碼描述性不強
4. 不要指望樣例幫你 debug。學著自己生成測試數據
5. 不管你是搞OI/ACM,還是做做這類題鍛煉思維,相信我,這將是你美妙的回憶
既然題主直接貼代碼求解答。。。
那我也直接貼代碼做為答案吧~~哈哈~~
個人建議lz自己調試。治愈卡在了哪裏,lz可以在可能卡主的地方(附近)添加printf(打印上下文,或者隻是標記都行)。這樣lz就可以確定程序到底跑到哪裏的時候出問題了。