C语言分治法求最近对问题 运行一直报错 求高手修改

Question

#include<stdio.h>
#include<math.h>
//using namespace std
//using namespace std;
#define MAX 100000000
#define N 100000
struct Point
{
double x,y;
};
Point S[N*2],S1[N],S2[N],P1[N],P2[N];
double Dis(Point a,Point b)
{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.y-b.y));}
int CMP1(Point a,Point b)
{return a.x<b.x;}
int CMP2(Point a,Point b)
{return a.y <b.y;}
double min(double a,double b)
{double c;
if(a>b)
{c=b;}
return c;}
double ClosePoint(Point S[],int n)
{if(n<2) return MAX;
else{
double d0=MAX;
int i,j,m;
int j1=0,j2=0;
double d1,d2,d;
int k1=0;
int k2=0;
sort(S,S+n,CMP1);
Point p=S[n/2];
m=p.x;
for(i=0;i<(n+1)/2;i++)
{S1[j1].x=S[i].x;
S1[j1].y=S[i].y;
j1++;}//构造S1中点坐标小于m
for(i=(n+1)/2;i<n;i++)
{S2[j2].x=S[i].x;
S2[j2].x=S[i].y;}//构造S2中点大于m
d1=ClosePoint(S1,j1);
d2=ClosePoint(S2,j2);
d=min(d1,d2);
for(i=0;i<j1;i++)
{if(m-S1[i].x<d)
{P1[k1].x=S1[i].x;
P2[k2].y=S1[i].y;
k1++;}}
for(i=0;i<j2;i++)
if(S2[i].x-m<d)
{P2[k2].x=S2[i].x;
P2[k2].y=S2[i].y;
k2++;
}
sort(P1,P1+k1,CMP2);
sort(P2,P2+k2,CMP2);
for(i=0;i<k1;i++)
{for(j=0;j<k2;j++)
{double A=Dis(P1[i],P2[j]);
d0=min(d0,A);}}
return min(d0,d);}
int main()
{int n;
printf("请输入端点的个数:\n");
scanf("%d",&n);
printf("请输入端点的坐标:\n");
for(int i=1;i<=n;i++)
{scanf("%d",&S[i].x);
scanf("%d",&S[i].y);}
double d=ClosePoint(S[i],n);
printf("最短距离为:%d",d);}

Answer 1

#include<stdio.h>
#include<math.h>
//using namespace std
//using namespace std;
#define MAX 100000000
#define N 100000
typedef struct Point
{
double x,y;
}Point;
Point S[N*2],S1[N],S2[N],P1[N],P2[N];
double Dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.y-b.y));
}
int CMP1(Point a,Point b)
{
return a.x<b.x;
}
int CMP2(Point a,Point b)
{
return a.y <b.y;
}
double min(double a,double b)
{
double c;
if(a>b)
{
c=b;
}
return c;
}
void sort(Point *p1,Point *p2,int (* cmp)(Point a,Point b))
{
//这个函数你自己添加吧

}
double ClosePoint(Point S[],int n)
{
if(n<2)
return MAX;
else
{
double d0=MAX;
int i,j,m;
int j1=0,j2=0;
double d1,d2,d;
int k1=0;
int k2=0;
sort(S,S+n,CMP1);
Point p=S[n/2];
m=p.x;
for(i=0;i<(n+1)/2;i++)
{
S1[j1].x=S[i].x;
S1[j1].y=S[i].y;
j1++;
}//构造S1中点坐标小于m
for(i=(n+1)/2;i<n;i++)
{
S2[j2].x=S[i].x;
S2[j2].x=S[i].y;
}//构造S2中点大于m
d1=ClosePoint(S1,j1);
d2=ClosePoint(S2,j2);
d=min(d1,d2);
for(i=0;i<j1;i++)
{
if(m-S1[i].x<d)
{
P1[k1].x=S1[i].x;
P2[k2].y=S1[i].y;
k1++;
}
}
for(i=0;i<j2;i++)
if(S2[i].x-m<d)
{
P2[k2].x=S2[i].x;
P2[k2].y=S2[i].y;
k2++;
}
sort(P1,P1+k1,CMP2);
sort(P2,P2+k2,CMP2);
for(i=0;i<k1;i++)
{
for(j=0;j<k2;j++)
{
double A=Dis(P1[i],P2[j]);
d0=min(d0,A);
}
}
return min(d0,d);
}
}
int main()
{
int n;
int i;
double d;
printf("请输入端点的个数:\n");
scanf("%d",&n);
printf("请输入端点的坐标:\n");
for(i=1;i<=n;i++)
{
scanf("%lf",&S[i].x);
scanf("%lf",&S[i].y);
}
d=ClosePoint(&S[i],n);
printf("最短距离为:%lf\n",d);
}追问

谢谢哈 现在没有错了，但是要是按照把所有点横坐标x递增排列的话怎么做？就是sort里面的东西

追答

那就比较Point中的x的值，然后按照要求换位置（或不换位置）就OK了

追问

我不太会用指针，你帮我写一下吧 谢谢~

Answer 2

mark一下