Question

杭电acm第1007题，为什么运行错误，下面是我的代码

#include<stdio.h>
#include<math.h>
int main()
{
double x[10000],y[10000],h[10000],tem,min;
int n,i,j,k;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(i=0;i<n;i++)
for(j=0;j<n-i-1;j++)
{
if(x[j]>x[j+1])
{
tem=x[i];
x[i]=x[i+1];
y[i]=tem;
tem=y[i];
y[i]=y[i+1];
y[i+1]=tem;
}
}
for(i=0;i<n-1;i++)
{
h[i]=sqrt((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1]));
if(i==0)
min=h[i];
else
{
if(min>h[i])
{
min=h[i];
}
}
}
printf("%0.2lf\n",min/2);
}
}

Answer 1

N (2 <= N <= 100,000)
数组开得不够大。而且你的代码即使运行不出错，答案也是不对的。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int N=1000000;
const double eps=0.00001; //精度
typedef struct TYPE
{
double x,y;
int index;
} Point; //存每点的坐标和索引值
Point a[N],b[N],c[N];
inline double min(double p,double q)
{
return p>q?q:p;
}
double dis(Point p,Point q)
{
double x1=p.x-q.x,y1=p.y-q.y;
return sqrt(x1*x1+y1*y1);
}
int merge(Point p[],Point q[],int s,int m,int t) //将数组q保存到p，且对y升序排序
{
int i,j,k;
for(i=s,j=m+1,k=s;i<=m&&j<=t;)
{
if(q[i].y>q[j].y)
p[k++]=q[j++];
else
p[k++]=q[i++];
}
while(i<=m)
p[k++]=q[i++];
while(j<=t)
p[k++]=q[j++];
memcpy(q+s,p+s,(t-s+1)*sizeof(p[0]));
return 0;
}
double closest(Point a[],Point b[],Point c[],int p,int q)
{
double dm=(double)INT_MAX,temp;
int i,j,k;
if(q-p<4){
for(i=p;i<q;i++){
for(j=i+1;j<=q;j++){
temp=dis(a[i],a[j]);
if(temp<dm)dm=temp;
}
}
return dm;
}
int m=(p+q)/2;

double d1,d2;
for(i=p,j=p,k=m+1;i<=q;i++)
if(b[i].index<=m)
c[j++]=b[i]; //数组左半部分保存划分的左部，对y升序的
else
c[k++]=b[i]; //数组右半部分保存划分的右部，对y升序的
d1=closest(a,c,b,p,m);
d2=closest(a,c,b,m+1,q);
dm=min(d1,d2);
merge(b,c,p,m,q); //将数组c保存到b，且对y升序的
for(i=p,k=p;i<=q;i++)
if(fabs(b[i].x-b[m].x)<dm)
c[k++]=b[i]; //将离划分线b[m].x距离不超过dm的部分保存到数组c
for(i=p;i<k;i++)
for(j=i+1;j<k&&c[j].y-c[i].y<dm;j++)
{
double temp=dis(c[i],c[j]);
if(temp<dm)
dm=temp;
}
return dm;
}
bool cmpx(Point a,Point b){
double temp=a.x-b.x;
if(temp>-0.00001)return false;
return true;
}
bool cmpy(Point a,Point b){
double temp=a.y-b.y;
if(temp>-0.00001)return false;
return true;
}
int main()
{
int n,i;
double d;
while(scanf("%d",&n)!=EOF&&n)
{
for(i=0;i<n;i++)
scanf("%lf %lf",&(a[i].x),&(a[i].y));
sort(a,a+n,cmpx);
for(i=0;i<n;i++)
a[i].index=i;
memcpy(b,a,n*sizeof(a[0]));
sort(b,b+n,cmpy);
d=closest(a,b,c,0,n-1); //求最近点对的距离
printf("%.2lf\n",d/2);
}
return 0;
}
我把自己AC的代码给你参考下。

追问

不会c++。。。。。

Answer 2

将数组的个数减少即可

追问

不行呀