編程的難題，我想解決以下問題這是一個程序設計大賽的一部分：與二進制搜索
問題ID：CIELLAND
廚師Ciel的發展與她的餐館一個新的島嶼。在島上，Ciel打算建立N家餐館，第i家餐廳的座標爲（xi，yi）。此外，Ciel將創建K路，其位置尚未確定。每條道路必須是無限長的直線。
讓di是第i家餐廳和最近的餐廳之間的距離。 Ciel希望創建最小化max（d1，d2，...，dN）的K道路。你的任務是計算max（d1，d2，...，dN）的最小值。
任何想法，我應該如何處理它？此外，比賽編輯出局（http://www.codechef.com/wiki/march-2012-cook-problem-editorials），但我不明白的解決方案。
任何關於要遵循的方法的幫助將不勝感激。
在高層次上，他們正在重新解決問題，以便更容易解決問題。通過投射在下面的光線，他們限制了可能的線路數量。
問題A：有N個圓圈。第i個圓的中心是（xi， yi）並且所有的圓都有半徑R.讓我們可以畫出X行，例如 任何圓與至少一條直線相交。什麼是最小的 X？
爲了進一步解釋，讓我們用言語改寫問題A：餐廳是規則的堅持者，並且有一條規則規定所有餐館必須同意距離道路的最大距離 - 這將是R.由餐廳和R創建的圓代表線需要相交以滿足此要求的地方。新問題要求最少數量的道路來做到這一點。
如果這在K道路下是不可能的，那麼一定要改變。我們不能根據原始問題添加道路，但是我們可以修改R.這是二進制搜索的來源，但我們必須首先解決問題A.
現在，讓我們考慮解決問題A.首先，行可以是 限於兩個圓的共同切線。因爲如果一條線 與一些（至少2個）圓相交，我們可以移動線如 ，移動的線與相同的圓相交，並且移動的線 是常用切線之一。如果一條線相交少於2個圓，則它是無用的（但要注意N = 1的情況）。最多有兩條線與兩個圓相切，所以我們最多考慮2條線，即N *（N-1）行。
重要的是這個，我們需要找到與多個圓相交的直線。每對圓圈最多需要考慮四行，請查看源代碼的實現。
接下來的一大步是找到覆蓋所有圈子的最少行數的動態規劃。'mask'是一個位掩碼，指示在考慮每條線時哪些圓圈已經被擊中。
這解決了這個問題，但現在我們必須轉換回來。記得R？我們現在可以進行二分搜索以找到最小R，使得X < = K。根據我對問題A的重新定義，其所有餐廳都會同意並保持最小距離
希望幫助，棘手但有趣的問題。
「重要的部分是這樣的，我們需要找到相交多於一個圓的線，每個圓最多需要考慮四條線」。我很抱歉，但我沒有完全明白。我認爲你說線需要交叉多於一個圓，否則線不會給我們所需的最小線。我對嗎 ？爲什麼從每一對考慮最多4條線呢？ – arya 2012-03-21 06:17:46
除非只有一個城市，否則我們需要一條線來至少交兩圈。如果一條直線與一個圓相交，則不值得考慮該直線，因爲還有一些其他圓可以相交併且仍然與該直線相交。如果這更容易，可以把它看成兩點 - 總是有一條線與兩點相交。 4條線是由兩個圓的共同切線組成的線。你可以嘗試證明這個數字不超過4，這對我來說很難在沒有繪製的情況下進行。 – dfb 2012-03-21 06:23:14
您是否熟悉旅行商問題？這似乎是一個變種;一般來說，這是一種動態編程問題。 – Marcin 2012-03-20 12:19:32
我想補充說，鏈接的解決方案顯然不是寫得很容易和快速理解。嘗試通過它。 – Marcin 2012-03-20 12:20:56
這個問題看起來像[聚類分析]（http://en.wikipedia.org/wiki/Cluster_analysis）和[Voronoi圖表]（http://en.wikipedia.org/wiki/Voronoi_diagram）。我的想法是修改[k-均值聚類]（http://en.wikipedia.org/wiki/K-means_clustering）或其他[動態編程]（http://en.wikipedia.org/wiki/ Dynamic_programming）技術。 – 2012-03-20 12:08:27