HDU 1007Quoit Design(最近點問題)

<code>最近點問題：二維平面中有n（n很大）個點，求出距離最近的兩個點</code>

<code>    </code> 

<code>    </code><code>思路：因為n的值很大，是以暴力和dp都行不通了吧！分治法就挺好的。</code>

<code>    </code><code>将區間一半一半的分開，直到分成隻有一個點或兩個點的時候！</code>

<code>    </code><code>對于隻有兩個點的區間，最小值就是這兩個點的距離，隻有一個點的區間，</code>

<code>    </code><code>最小值就是無窮大。注意還要考慮合并的時候，可能距離最近的兩個點，</code>

<code>    </code><code>分别在左右兩個不同的區間。對于這種情況的處理如下：</code>

<code>         </code><code>mid=(ld+rd)/2;</code>

<code>         </code><code>ans = min(solve(ld, mid), solve(mid+1, rd));得到兩段區間最小值的最小值</code>

<code>        </code><code>從中間向兩邊尋找，因為我們是按照x坐标排序的，在左區間向左邊尋找的時候</code>

<code>        </code><code>如果某一個點的x到中間點x的距離大于ans（否則将這樣的點儲存），那麼這個</code>

<code>        </code><code>點左邊的點就不可能在右區間尋找到相應的點滿足兩個點的距離小于ans的，那麼</code>

<code>        </code><code>就結束繼續查找（這樣算是一種優化）</code>

<code>        </code> 

<code>        </code><code>同理在右區間向右尋找。。。</code>

<code>        </code><code>然後對存儲的節點按照y坐标進行從小到大的排序。</code>

<code>        </code><code>枚舉每兩個點尋找最小的距離</code>

<a></a>

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/4348418.html，如需轉載請自行聯系原作者