中南大学算法设计与分析实验报告

《中南大学算法设计与分析实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、姓名：学号：0909122824班级：信安1202指导老师：李敏算法设计与分析基础——实验报告实验一分治—最近点对一．问题ProblemHaveyoueverplayedquoitinaplayground?Quoitisagameinwhichflatringsarepitchedatsometoys,withallthetoysencircledawarded.InthefieldofCyberground,thepositionofeachtoyisfixed,andtheringiscarefullydesignedsoitcanonlyencircleonetoyata

2、time.Ontheotherhand,tomakethegamelookmoreattractive,theringisdesignedtohavethelargestradius.Givenaconfigurationofthefield,youaresupposedtofindtheradiusofsucharing.Assumethatallthetoysarepointsonaplane.Apointisencircledbytheringifthedistancebetweenthepointandthecenteroftheringisstrictlylesstha

3、ntheradiusofthering.Iftwotoysareplacedatthesamepoint,theradiusoftheringisconsideredtobe0.InputTheinputconsistsofseveraltestcases.Foreachcase,thefirstlinecontainsanintegerN(2<=N<=100,000),thetotalnumberoftoysinthefield.ThenNlinesfollow,eachcontainsapairof(x,y)whicharethecoordinatesofatoy.Thein

4、putisterminatedbyN=0.OutputForeachtestcase,printinonelinetheradiusoftheringrequiredbytheCybergroundmanager,accurateupto2decimalplaces.二．分析思路题目是给n个点的坐标，求距离最近的一对点之间距离的一半。第一行是一个数n表示有n个点，接下来n行是n个点的x坐标和y坐标。首先，假设点是n个，编号为1到n。找一个中间的编号mid，先求出1到mid点的最近距离设为d1，还有mid+1到n的最近距离设为d2。如果说最近点对中的两点都在1-mid集合中，或者m

5、id+1到n集合中，则d就是最小距离了。但是还有可能的是最近点对中的两点分属这两个集合，若存在，则把这个最近点对的距离记录下来，去更新d。这样就得到最小的距离d了。三．源代码#include#include#includeusingnamespacestd;#defineN1000010structpoint{doublex;doubley;}p1[N],p2[N];doubledis(pointa,pointb){returnsqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));}doublemin(do

6、ublea,doubleb){returna

7、in(mindis(l,mid),mindis(mid+1,r));for(inti=l;i<=r;i++){if(fabs(p1[i].x-p1[mid].x)<=mini)p2[count++]=p1[i];}sort(p2,p2+count,cpy);for(inti=0;i=mini)break;elseif(dis(p2[j],p2[i])