資源描述:
《中南大學算法設計與分析實驗報告》由會員上傳分享,免費在線閱讀,更多相關內(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])