从给定的坐标集中查找矩形的数量

我必须从给定的一组坐标中找到最大数量的矩形。从给定的坐标集中查找矩形的数量

考虑以下坐标的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

从给定的坐标集中查找矩形的数量

回答

相关问题