中南大學算法設計與分析實驗報告

《中南大學算法設計與分析實驗報告》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

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個點的坐標，求距離最近的一對點之間距離的一半。第一行是一個數(shù)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])