1樓：龍陽桑
？ 是我沒有看懂題目嗎？
題目不是問的「是否」存在且至少m個點在給定的圓內嗎？
答案肯定是不一定啊。
就拿英雄聯盟來說啊。 你在自家泉水畫圓，對面五個點在對方泉水呆著。顯然除非這個圓至少外接召喚師峽谷（預設召喚師峽谷為矩形），才能保證一定有點落在圓內，顯然不可能。
（如果定義死歌大招是這樣乙個只以英雄為目標的圓確實有可能）
所以，就按題目這種敘述，題目一定是假命題。
問的是給定r圓，平面n個點有至少m個在圓內的概率，那估計上面大神的回答才對（我不懂概率論→_→）
2樓：weald
這是我目前想到的最好答案~
遍歷第 i個點 ，並作為原點以r為半徑遍歷其他點 j （從i開始到n）並判斷是否覆蓋，如果覆蓋的話，計數陣列q（i）++ ， q（j）++，結束後判斷q 陣列中有無大於m的數，有大於的數說明存在這樣乙個半徑為r的圓，否則沒有
時間複雜度表示式 （ 1+n）n/ 2 + n
3樓：好地方bug
將每個點擴充套件成半徑為r的圓，那麼平面上必有一些區域被乙個或多個圓覆蓋，如果乙個區域被覆蓋了k次，那麼以這個區域內任意一點做半徑為r的圓，一定能覆蓋k個點。
所以只用找到覆蓋次數最多的區域。
這時候依次以每個點當做原點，對這個點的擴充套件圓的交點做極角排序，最後掃一遍就好了。
複雜度n^2logn
以上為原答案，由於之前用手機打的，所以寫的不是很清楚。
我是分割線
按照題目意思我們有個平面，上面有 個點：
這裡我畫了三個點，現在我們把這三個點擴充套件成半徑為 的三個圓：
圖上的數字表示被覆蓋了幾次，在寫1的地方，我們任意做乙個半徑為$R$的圓，一定能包含乙個點，在寫2的地方，我們做乙個半徑為 的圓，一定能包含兩個點，所以我們只用找到被覆蓋次數最多的區域。
依次考慮每個點的擴充套件圓，比如我們先考慮最下面的那個點的擴充套件圓，把它和其它擴充套件圓的交點計算出來（橙色的點），如下圖所示：
為了便於統計，我們把橙色的點按照圓心極角排序，以逆時針方向依次標記每個交點，如果是進入乙個圓的交點，就標記+1，否則-1，如下圖所示：
接下來，沿著逆時針方向掃一遍，就能知道每段弧被覆蓋了多少次：
這樣一來，我們就知道了這個圓參與的所有區域的覆蓋情況，用相同的方法處理每個圓，就能正確統計出答案了。
考慮一下複雜度：
由於我們需要考慮每個擴充套件圓的情況，所以首先有個 ，每個擴充套件圓需要找到所有這個擴充套件圓的交點，最多 個，將這些交點排序，多個 ，所以最後的複雜度是
4樓：yaoyao
勾股定理不會還給老師了吧？
遍歷n，把n的座標減去圓心座標的x,y的偏差的平方值相加小於r的平方的放入集合，最後這個集合的元素個數，就是m。時間複雜度是O(n)。
5樓：Sunshower
平面內3點即可確定乙個圓。
若m＝1，r≧0即可；
若m＝2，r≧兩點連線即可；
若m＝3，計算確定圓的半徑判斷即可；
若m≧4，
做個圈自己套著試吧
6樓：Bila
你先說下玩家怎麼操作來釋放這個技能，先不用管能不能放。
我理解的是，一般aoe都會有提示圈，意味著玩家會弄出乙個中心點來作為基準。提前把地圖網格化，單位位置變動時更新單位的網格位置。這樣，從中心點出發，按半徑搜格仔裡的單位，計算量不大。
7樓：
想要降低複雜度也可以網格化，即update時更新自己的grid座標資訊，檢查距離時僅檢查半徑內的grid，複雜度o(r^2), 適用於大地圖多單位，速度近似為常量，可以任意增大地圖面積和單位數量不影響速度
平面上有N個點，如何選出3個點，使得他們組成的三角形面積最小 最大？
張一釗 面積最大的三角形顯然在凸包上，轉化為凸包的最大內接三角形的經典問題，可以 時間解決。最小三角形覺得列舉乙個點然後掃瞄線搞搞還是可以很容易 的。下午考慮一下。填坑。懶得去文獻檢索了，說自己腦補的乙個 的簡單演算法。設所有的點為 不妨設沒有三點共線。對於每一對點 考慮與 垂直的方向 稱為關鍵方向...
在平面上，是否存在三個點，使平面上任意一點與三點中至少一點的距離為無理數？
晚風 這個問題很簡單，幹嘛考慮得那麼複雜？實際上就是，平面上乙個點到另乙個點距離為無理數 如 2 其餘兩個點隨便取，與題目無關。你去畫乙個直角邊長為1的等腰直角三角形，我可以負責任地告訴你，斜邊長就是 2。也就是說，斜邊兩端點的距離為 2。以此類推，距離是 3，5 都可以通過直角三角形 勾股定理輕而...
平面上有n個不同點，它們之間至少有多少個不同距離？
暮鼓晨鐘 記得這是個11年才被解決的問題？答案應該是 級別的 不保證對 構造的話考慮乙個 接近 的點陣即可 當然驗證起來也不是那麼容易 證明的話就要用很多我還不會的東西了。似乎11年CTST還考了相關的小結論呢。這題確定當大一新生考試題？可能只能面試問一下，考考構造的反應速度吧。 言水 我錯了現在我...