HDU1007 Quoit Design

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1007

具体算法分析见：最接近点对问题

版本一：

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
usingnamespacestd;
constintN=100005;
constdoubleMAX=10e100;
constdoubleeps=0.00001;
typedefstructTYPE
{
doublex,y;
intindex;
}Point;
Pointa[N],b[N],c[N];
doubleclosest(Point*,Point*,Point*,int,int);
doubledis(Point,Point);
intcmp_x(constvoid*,constvoid*);
intcmp_y(constvoid*,constvoid*);
intmerge(Point*,Point*,int,int,int);
inlinedoublemin(double,double);

intmain()
{
intn,i;
doubled;
scanf("%d",&n);
while(n)
{
for(i=0;i<n;i++)
scanf("%lf%lf",&(a[i].x),&(a[i].y));
qsort(a,n,sizeof(a[0]),cmp_x);
for(i=0;i<n;i++)
a[i].index=i;
memcpy(b,a,n*sizeof(a[0]));
qsort(b,n,sizeof(b[0]),cmp_y);
d=closest(a,b,c,0,n-1);
printf("%.2lf/n",d/2);
scanf("%d",&n);
}
return0;
}

doubleclosest(Pointa[],Pointb[],Pointc[],intp,intq)
{
if(q-p==1)
returndis(a[p],a[q]);
if(q-p==2)
{
doublex1=dis(a[p],a[q]);
doublex2=dis(a[p+1],a[q]);
doublex3=dis(a[p],a[p+1]);
if(x1<x2&&x1<x3)
returnx1;
elseif(x2<x3)
returnx2;
else
returnx3;
}
intm=(p+q)/2;
inti,j,k;
doubled1,d2;
for(i=p,j=p,k=m+1;i<=q;i++)
if(b[i].index<=m)
c[j++]=b[i];
//数组c左半部保存划分后左部的点,且对y是有序的.
else
c[k++]=b[i];
d1=closest(a,c,b,p,m);
d2=closest(a,c,b,m+1,q);
doubledm=min(d1,d2);
merge(b,c,p,m,q);//数组c左右部分分别是对y坐标有序的,将其合并到b.
for(i=p,k=p;i<=q;i++)
if(fabs(b[i].x-b[m].x)<dm)
c[k++]=b[i];
//找出离划分基准左右不超过dm的部分,且仍然对y坐标有序.
for(i=p;i<k;i++)
for(j=i+1;j<k&&c[j].y-c[i].y<dm;j++)
{
doubletemp=dis(c[i],c[j]);
if(temp<dm)
dm=temp;
}
returndm;
}

doubledis(Pointp,Pointq)
{
doublex1=p.x-q.x,y1=p.y-q.y;
returnsqrt(x1*x1+y1*y1);
}

intmerge(Pointp[],Pointq[],ints,intm,intt)
{
inti,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],j++;
else
p[k++]=q[i],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]));
return0;
}

intcmp_x(constvoid*p,constvoid*q)
{
doubletemp=((Point*)p)->x-((Point*)q)->x;
if(temp>0)
return1;
elseif(fabs(temp)<eps)
return0;
else
return-1;
}

intcmp_y(constvoid*p,constvoid*q)
{
doubletemp=((Point*)p)->y-((Point*)q)->y;
if(temp>0)
return1;
elseif(fabs(temp)<eps)
return0;
else
return-1;
}

inlinedoublemin(doublep,doubleq)
{
return(p>q)?(q):(p);
}

版本二：（使用STL，未能AC掉,还得继续测试。。。）

<!--<br /> <br /> Code highlighting produced by Actipro CodeHighlighter (freeware)<br /> http://www.CodeHighlighter.com/<br /> <br /> -->#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iomanip>
usingnamespacestd;

constdoubleeps=0.00001;

classpoint
{
public:
point(doublex1=0.0f,doubley1=0.0f,intid=0):x(x1),y(y1),id(id)
{
}
~point()
{
}
doublegetX()const
{
returnx;
}
doublegetY()const
{
returny;
}
voidsetID(intt)
{
id=t;
}
doublegetID()const
{
returnid;
}
doubleDistance(constpoint&rhs)
{//计算与另外一个点之间的距离
doubledx=(x-rhs.x);
doubledy=(y-rhs.y);
returnsqrt(dx*dx+dy*dy);
}
friendostream&operator<<(ostream&out,constpoint&rhs)
{
out<<rhs.x<<""<<rhs.y<<"idis:"<<rhs.id<<endl;
returnout;
}
booloperator<(constpoint&rhs)
{
returnx<rhs.x;
}
point&operator=(constpoint&rhs)
{
x=rhs.x;
y=rhs.y;
id=rhs.id;
return*this;
}
private:
doublex;
doubley;
intid;//点的编号
};

boolcmp_onY(constpoint&p,constpoint&q)
{
returnp.getY()<q.getY();
}

doublemin(constdouble&a,constdouble&b)
{
returna<b?a:b;
}
voidprintVector(vector<point>&v)
{
vector<point>::iteratoriter;
for(iter=v.begin();iter!=v.end();++iter)
{
cout<<*iter<<endl;
}
}
intmerge(vector<point>&a,vector<point>&b,intbegin,intmid,intend)
{//合并
inti,j,k;
for(i=begin,j=mid+1,k=begin;i<=mid&&j<=end;)
{
if(b[i].getY()>b[j].getY())
a[k++]=b[j],j++;
else
a[k++]=b[i],i++;
}
while(i<=mid)
a[k++]=b[i++];
while(j<=end)
a[k++]=b[j++];
vector<point>::iteratoriter=a.begin();
copy(iter+begin,iter+(end-begin+1),b.begin());
return0;
}
doubleClosest(vector<point>&a,vector<point>&b,vector<point>&c,intbegin,intlast)
{
intlen=last-begin;
if(len==1)
{//只有两个了
returna[begin].Distance(a[last]);
}
if(len==2)
{//还有三个
doublet1=a[begin].Distance(a[last]);
doublet2=a[begin].Distance(a[begin+1]);
doublet3=a[begin+1].Distance(a[last]);
if(t1<t2&&t1<t3)
returnt1;
elseif(t2<t3)
returnt2;
else
returnt3;
}
intmid=(begin+last)/2;//分割点
inti,j,k;
doubled1,d2;
for(i=begin,j=begin,k=mid+1;i<=last;++i)
{
if(b[i].getID()<=mid)
c[j++]=b[i];
else
c[k++]=b[i];
}
d1=Closest(a,c,b,begin,mid);
d2=Closest(a,c,b,mid+1,last);
doubledm=min(d1,d2);
merge(b,c,begin,mid,last);
for(i=begin,k=begin;i<=last;++i)
if(fabs(b[i].getX()-b[mid].getX())<dm)
c[k++]=b[i];
for(i=begin;i<k;++i)
for(j=i+1;j<k&&(c[j].getY()-c[i].getY()<dm);j++)
{
doubletemp=c[i].Distance(c[j]);
if(temp<dm)
dm=temp;
}
returndm;
}
intmain()
{
intnPoints,i;
doublex1,y1,result=0.0f;
vector<point>v1,v2,v3;
while(cin>>nPoints&&nPoints!=0)
{
for(i=0;i<nPoints;++i)
{
cin>>x1>>y1;
pointtmp(x1,y1);
v1.push_back(tmp);
}
v3=v1;
sort(v1.begin(),v1.end());
for(i=0;i<nPoints;++i)
{
v1[i].setID(i);
}
v2=v1;
sort(v2.begin(),v2.end(),cmp_onY);
result=Closest(v1,v2,v3,0,nPoints-1);
cout<<setiosflags(ios::fixed)<<setprecision(2);
cout<<result/2<<endl;
v1.erase(v1.begin(),v1.end());
v2.erase(v2.begin(),v2.end());
v3.erase(v3.begin(),v3.end());
}
return0;
}