zuixindi.cpp

最接近点对问题

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<graphics.h>
#include<math.h>
main()
{
int paixu(int n,int a[100],int b[100]);
void paixu2(int n,int a[100],int b[100]);
int paixu3(int n,int a[100]);
int a[100],b[100],x[100],y[100],x1[100],x2[100],y1[100],y2[100],dm[100],p1x[100],p1y[100],p2x[100],p2y[100],midd[100];
int x1m[100],y1m[100],x2m[100],y2m[100];
int d[100][100];
int middle,total,z,n,i,j,p,q,d1,d2,r,s,d3,v;
p=q=r=s=v=0;
int Driver=DETECT,Mode;
initgraph(&Driver,&Mode,"f:\\tc3\\bgi");
printf("please input n:");
scanf("%d",&n);
randomize();
for(i=0;i<n;i++)
  {
   x[i]=random(100);
   y[i]=random(100);
   printf("%4d%4d",x[i],y[i]);
  }

for(i=0;i<n;i++)
  {
   putpixel(x[i]+200,y[i]+200,2);
  }
total=0;
for(i=0;i<=n-1;i++)
  {
  total=total+x[i];
  }
printf("\n");
printf("%4d",total);
printf("\n");
middle=total/n;
printf("%4d",middle);
printf("\n");
for(i=0;i<n;i++)
   {
  if(x[i]<middle)
     {
     x1[p]=x[i];
     y1[p]=y[i];

     p++;
     }
  else
     {
     x2[q]=x[i];
     y2[q]=y[i];

     q++;
     }
   }
printf("%4d%4d",p,q);
printf("\n");
d1=paixu(p,x1,y1);
d2=paixu(q,x2,y2);
if(d1<d2)
  d3=d1;
else
  d3=d2;
for(i=0;i<p;i++)
   {
   if(middle-x1[i]<d3)
   x1m[r]=x1[i];
   y1m[r]=y1[i];
   r++;
   }
   paixu2(r,x1m,y1m);

for(i=0;i<q;i++)
  {
  if(x2[i]-middle<d3)
  x2m[s]=x2[i];
  y2m[s]=y2[i];
  s++;
  }
paixu2(s,x2m,y2m);
for(i=0;i<r;i++)
   {
   for(j=0;j<s;j++)
     {
     if(y1m[i]-y2m[j]<d3)
       {
       midd[v]=sqrt(pow((x1m[i]-x2m[j]),2.00)+pow((y1m[i]-y2m[j]),2.00));
       v++;
       }
      }
   }
z=paixu3(v,midd);
if(z<d3)
printf("\nthe zuixiao juli is %4d",z);
else
printf("\nthe zuixiao juli is %4d",d3);

printf("\n");

  getch();
  return 0;
}
int paixu(int n,int a[100],int b[100])
{
int dm[100];
int d[100][100];
int d1;
int i,j,w,m;
m=0;

if(n==1)
printf("error/n");
if(n==2)
  {
  dm[0]=sqrt(pow((a[1]-a[0]),2.00)+pow((b[1]-b[0]),2.00));
  }
else
  {
  for(i=0;i<n;i++)
    {
    for(j=0;j<n;j++)
      {
       d[i][j]=sqrt(pow((a[j]-a[i]),2.00)+pow((b[j]-b[i]),2.00));
       printf("%4d",d[i][j]);
      }
    }
  }
for(i=n-1;i>0;i--)
  {
   for(j=0;j<i-1;j++)
      {
      if(d[i][0]>d[i][j+1])
     {
      w=d[i][0];
      d[i][0]=d[i][j+1];
      d[i][j+1]=w;
      }
      }
      dm[m]=d[i][0];
      m++;
  }
for(m=0;m<n-2;m++)
  {
  if(dm[0]>dm[m+1])
    {
     w=dm[0];
     dm[0]=dm[m+1];
     dm[m+1]=w;
    }
  }
return dm[0];
}
void paixu2(int n,int a[100],int b[100])
{
int i,j,k,w,s;
for(i=0;i<n-1;i++)
  {
   k=i;
   for(j=0;j<n-k-1;j++)
     {
     if(b[j]>b[j+1])
       {
       w=b[j+1];
       s=a[j+1];
       b[j+1]=b[j];
       a[j+1]=a[j];
       b[j]=w;
       a[j]=s;
       }
     }
   }

}
int paixu3(int n,int a[100])
{
int i,w;
for(i=0;i<n;i++)
  {
  if(a[i]>a[i+1])
    {
     w=a[i];
     a[i]=a[i+1];
     a[i+1]=w;
    }
  }
return a[0];
}