# 求最近点对 栈溢出有关问题 杭电1007

www.MyException.Cn  网友分享于：2013-03-04  浏览：24次

http://acm.hdu.edu.cn/showproblem.php?pid=1007
C/C++ code
```#include<iostream.h>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;

#define max 100005//100000

struct Point
{
double x;
double y;
}p[max];

double Max(double a,double b)
{
if(a<b)
return b;
return a;
}
double Min(double a,double b)
{
if(a<b)
return a;
return b;
}

//Point p[max];
class ClosetPoint
{
private:
//保存点
int num;
public:
void Input(int iCount);//传进一个要输入的顶点数目iCount
// bool cmp_x(const Point& a,const Point& b);//比较排序
// bool cmp_y(Point a,Point b);
double Seprate(int start,int end);//分治
double Merge(double curmin,int start,int end);
double Distance(Point a,Point b);
};

/*bool ClosetPoint::*/cmp_x(Point a, Point b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}

/*bool ClosetPoint::*/cmp_y(Point a,Point b)
{
if(a.y!=b.y)
return a.y<b.y;
else
return a.x<b.x;
}

void ClosetPoint::Input(int iCount)//接受输入的顶点信息
{

num =iCount;
for(int i =0;i<iCount;i++)
cin>>p[i].x>>p[i].y;
sort(p,p+num,cmp_x);
}

double ClosetPoint::Distance(Point a,Point b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}

double ClosetPoint::Seprate(int start,int end)//分治的起始位置
{
if(end-start==1)
return Distance(p[start],p[end]);
else if(end-start==2)
{
double temp1=Distance(p[start],p[start+1]);
double temp2=Distance(p[start],p[end]);
double temp3=Distance(p[start+1],p[end]);
double temp= Max(temp1,temp2);
return Max(temp,temp3);
}

int mid =(start+end)/2;
double dlm=Seprate(start,mid);
double drm=Seprate(mid+1,end);

return Min(dlm,drm);
}

double ClosetPoint::Merge(double curmin,int start,int end)
{
Point Yp[max];
int mid = (start+end)/2;
int j=0;
for(int s=0;s<num;s++)
{
if(fabs(p[s].x-p[mid].x)<=curmin)
{
Yp[j].x=p[s].x;
Yp[j++].y=p[s].y;
}
}
sort(Yp,Yp+j,cmp_y);
for(int i=0;i<j;i++)
{
for(int k=i+1;k<i+7&&k<j;k++)
{
if(Distance(Yp[i],Yp[k])<curmin)
{
curmin = Distance(Yp[i],Yp[k]);
}
}
}
return curmin;
}

int main()
{
ClosetPoint cp;
int iCount;
while(cin>>iCount)
{
if(iCount==0)
break;
cp.Input(iCount);
double curmin = cp.Seprate(0,iCount-1);
double min = cp.Merge(curmin,0,iCount-1);
// cout<<fixed<<setprecision(2)<<min<<endl;
cout.precision(2);
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout<<min/2<<endl;
}
/*    Point p1,p2;
p1.x=0;
p1.y=0;
p2.x=1;
p2.y=1;
cout<<cp.Distance(p1,p2)<<endl; //test Distance method*/
return 0;
}

```

------解决方案--------------------

<1>通过new或者malloc或使用API在内存堆中分配，记得不用时要销毁
<2>使用CreateFileMapping和MapViewOfFile映射内存文件的方式分配空间，同样不用时要反映射
------解决方案--------------------
double ClosetPoint::Merge(double curmin,int start,int end)
{
Point Yp[max];

------------------->
Point* Yp = new Point[max];