最近點對問題定義：已知上m個點的集合，找出對接近的一對點。 ? ? ?在二維空間里，可用分治法求解最近點對問題。預處理：分別根據點的x軸和y軸坐標進行排序，得到X和Y,很顯然此時X和Y中的點就是S中的點。 情況（1）：點數小于等于三時：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

情況（2）：點數大于三時： ?????首先劃分集合S為SL和SR，使得SL中的每一個點位于SR中每一個點的左邊，并且SL和SR中點數相同。分別在SL和SR中解決最近點對問題，得到DL和DR，分別表示SL和SR中的最近點對的距離。令d=min(DL,DR)。如果S中的最近點對(P1,P2)。P1、P2兩點一個在SL和一個在SR中，那么P1和P2一定在以L為中心的間隙內，以L-d和L+d為界，如下圖所示：

? ? ? ? ? ? ? ? ? ? ? ?

?????如果在SL中的點P和在SR中的點Q成為最近點對，那么P和Q的距離必定小于d。因此對間隙中的每一個點，在合并步驟中，只需要檢驗yp+d和yp-d內的點即可。 步驟1：根據點的y值和x值對S中的點排序。 步驟2：找出中線L將S劃分為SL和SR 步驟3：將步驟2遞歸的應用解決SL和SR的最近點對問題，并令d=min(dL,dR)。 步驟4：將L-d~L+d內的點以y值排序，對于每一個點(x1,y1)找出y值在y1-d~y1+d內的所有點，計算距離為d'。 ? ? ? ? ? ? ? ? 如果d'小于d，令d=d'，最后的d值就是答案。
參考博客：http://www.cnblogs.com/AdaByron/archive/2011/10/07/2200966.html

總結

以上是生活随笔為你收集整理的hdu 1007(最近点对)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。