1樓：張一釗
面積最大的三角形顯然在凸包上，轉化為凸包的最大內接三角形的經典問題，可以 時間解決。
最小三角形覺得列舉乙個點然後掃瞄線搞搞還是可以很容易 的。下午考慮一下。
填坑。。。懶得去文獻檢索了，說自己腦補的乙個 的簡單演算法。
設所有的點為 。不妨設沒有三點共線。對於每一對點 ，考慮與 垂直的方向 （稱為關鍵方向），共得到 個關鍵方向。將關鍵方向按極角順序排序。
初始時，按某個非關鍵方向的任意的方向 將所有點排序（即按 排序）。考慮把 按逆時針方向轉動，轉動起初對點的順序沒有影響。當其第一次與某個關鍵方向 重合時，發生兩件事情：
，因此第 個點與第 個點在序列中實際上處於同乙個位置。如果 繼續轉動，第 個點與第 個點在序列中交換位置。因此我們在每個關鍵方向處可以常數時間維護序列的順序。
由第 個點組成的三角形的面積為 。固定 為底邊，那麼使得三角形面積最小的 即是使 最小，因此一定為第 個點（第 個點）在序列中的前驅或後繼，可以直接查詢得到。
因此，在 轉過半圈後，我們就遍歷了所有的關鍵方向，也同時列舉了所有的點對作為底邊，在某個底邊的時候必然列舉到了答案。
好像有基於 Line Arrangement 的 的做法，感興趣的朋友可以自行查詢。
平面上有n個點，如何求其中是否至少有m個點在任意乙個半徑為r的圓內？
龍陽桑 是我沒有看懂題目嗎？題目不是問的 是否 存在且至少m個點在給定的圓內嗎？答案肯定是不一定啊。就拿英雄聯盟來說啊。你在自家泉水畫圓，對面五個點在對方泉水呆著。顯然除非這個圓至少外接召喚師峽谷 預設召喚師峽谷為矩形 才能保證一定有點落在圓內，顯然不可能。如果定義死歌大招是這樣乙個只以英雄為目標的...
在平面上，是否存在三個點，使平面上任意一點與三點中至少一點的距離為無理數？
晚風 這個問題很簡單，幹嘛考慮得那麼複雜？實際上就是，平面上乙個點到另乙個點距離為無理數 如 2 其餘兩個點隨便取，與題目無關。你去畫乙個直角邊長為1的等腰直角三角形，我可以負責任地告訴你，斜邊長就是 2。也就是說，斜邊兩端點的距離為 2。以此類推，距離是 3，5 都可以通過直角三角形 勾股定理輕而...
平面上有n個不同點，它們之間至少有多少個不同距離？
暮鼓晨鐘 記得這是個11年才被解決的問題？答案應該是 級別的 不保證對 構造的話考慮乙個 接近 的點陣即可 當然驗證起來也不是那麼容易 證明的話就要用很多我還不會的東西了。似乎11年CTST還考了相關的小結論呢。這題確定當大一新生考試題？可能只能面試問一下，考考構造的反應速度吧。 言水 我錯了現在我...