從給定的座標集中查找矩形的數量

我必須從給定的一組座標中找到最大數量的矩形。從給定的座標集中查找矩形的數量

考慮以下座標的XY給定座標系 3 10， 3 8， 3 6， 3 4， 3 0， 6 0， 6 4， 6 8， 6 10 ，

我怎麼能找到，如果以下座標形成一個矩形（3,0）（3,4）（6,4）（6,0）

運行時間限制：0.1秒

謝謝

來源

2013-10-05 Alin

決定什麼是問題。 4點形成一個矩形或在給定的點上可以形成多少個矩形？ – hasan83

他們兩人其實，我如何驗證4個點形成一個矩形，我如何找到最大數量的可能矩形 – Alin

這是一個ACM問題？ – hasan83

要檢查4個點形成一個矩形：

每兩個點計算的距離。將所有數據存儲在浮點數組中。
排序數組。

你將有一個[0] = A [1]，A [2] = [3]，A [4] = A [5]

來源

2013-10-05 22:22:21 hasan83

您的條件[需要但不夠]（https://en.wikipedia.org/wiki/Necessity_and_sufficiency）：[parallelorgram]（https://en.wikipedia.org/wiki/Parallelogram）也會滿足它。由於舍入誤差，比較浮點數以確切相等是一個壞主意。 – MvG

不，你錯了。平行句中的對角線並不等於 – hasan83

啊，錯過了那一點，對不起。感謝您的澄清。 – MvG

我怎麼能找到，如果以下座標形成一個矩形

檢查該差矢量是否是正交的，即具有點積爲零。

這是的不是檢查這些座標是否包含在您的列表中。它也沒有而不是檢查矩形是否與座標軸對齊，這將是一個更簡單的問題。

如果你想在你的輸入中找到所有的矩形，你可以可以做上述檢查所有的四倍。如果由於性能原因這是不可接受的，那麼您應該更新您的問題，指出您面臨的問題的大小和性能受到哪些限制。

來源

2013-10-05 22:20:17 MvG

獨立的在「Y的列表點'座標，按'x'座標分組。你的情況，你將有兩個有序列表：

3: [0,4,6,8,10] 
6: [0,4,8,10]

做兩份名單你得到的交集：[0,4,8,10]

任何兩個那些會形成一個矩形：

[0,4] => (3,0), (3,4), (6,0), (6,4) 
[0,8] => (3,0), (3,8), (6,0), (6,8) 
[4,8] => (3,4), (3,8), (6,4), (6,8) 
...

此解決方案僅適用於正交矩形，這是與x，y軸平行的邊。

來源

2013-10-28 21:38:12

令人驚訝的是，我一直在努力尋找一種方法來實現這一點 – AlvaroAV

從給定的座標集中查找矩形的數量

回答

相關問題