這個演算法如何設計

1樓：

我的大概思路這樣：

平面上有n個點。

根據假設「最優矩形包含第i個點」，可以把總問題分解為n個小問題。

在第i個小問題中，矩形必然包含第i個點。

為何稱之為「小」問題呢。因為「距離大於矩形對角線長度的點不可能在同一矩形內」，所以每個「小」問題都不需要考慮全部n點，只需要考慮第i點為圓心，對角線長為半徑內的若干個點，設k個點。，不同的小問題，k值一般是不同的。。

對於每個小問題，可以用窮舉法，不斷測試k個點中的某幾個能否被矩形包容。

然後每個小問題找出一個能包含最多點的矩形，，最後在所有小問題中，選出包點最多的一個矩形，就可以了。

小問題由於包含的點少，所以求解應該相對快。具體解法有待進一步研究。

2樓：匿名使用者

附帶提出兩個問題

a.界定.矩形線上的算在內還是在外.比如正方形四個角四個點,同尺寸的正方形來"圈",算4個點還是0個點.

b.等量.矩形在某處與另一處獲得同樣多的點.

c.解決問題中的角度問題,和窮舉有關.角度可無限細分.

誇張些假設,以10億光年的矩形斜對角為半徑來搜尋平面中的星球數.角度差之毫釐,星球失之nnn.這不算什麼極限問題,即使只有3個點也有可能產生嚴重衝突,恰巧某三點處於不斷細分的角度左右振盪之間並且是無限小數...

(多點的時候,衝突就更直接影響到真實數量)貌似不可解決:p

3樓：森浩瀚

如果要在程式中實現，不知道函式ptinrect是否會有幫助。

如果是討論演算法的問題。我有以下思路。

n個點連成的n(n-1)/2條線段中，只與矩形有一個交點的線的數量等於矩形外部的點的數量。這樣，與矩形只有一個交點的邊的數量最少即為所求。

一個給定大小的矩形的四條邊可表示為斜率k和一未知量b的方程。平面內各點座標已知。二元方程求最優，似乎可解。

沒有實踐，不知是否可行。

4樓：匿名使用者

看到了,進來看看.

好的辦法我是沒有,笨辦法不知道能不能用..

隨便那一個點a(x,y)

固定在矩形的頂點.然後旋轉360度.

這麼做可以覆蓋點一週的以長方形斜邊為半徑的圓也是它包含點a後,能覆蓋最大的面積.

通過旋轉360度來找出包含點數最多的矩形

然後把這個應用到每個點

就能找到包含點數最多的矩形了

5樓：匿名使用者

我不太清楚你的具體題目，不過如果點是隨機的就只能窮舉，而如果點很多就會非常考驗你的機器了。

窮舉的時候可以靠各個點的連線所圍成的面積最接近矩形面積來做，但要排除怪異形狀的超出矩形範圍的。

6樓：科技創意家

先找這些點所形成的物體重心的位置（應該是取三個點所形成的三角形的重心，然後找這些重心點形成的三角形重心，一直找下去），然後以此為矩形的中心，然後旋轉矩形看什麼情況下所包含點最多。