在最小矩形内找到点。O（n）但进一步优化
面试问题:
给定数十亿个矩形，找到与给定点P（x，y）重叠的最小面积矩形
有一种简单的方法通过顺序地处理每个矩形来在O（n）时间内实现答案，但进一步优化它提供了大量的矩形阵列。
我最好的方法是检查每个矩形，看看点是否在里面，然后计算面积并与当前最小的面积进行比较。这可以一次完成。我想不出任何其他不需要检查所有矩形的方法
共有3个答案
很可能你没有说出完整的问题。因为现在的情况，你的解决方案是最优的。
不管怎样，你都必须至少通过一个矩形来检查它是否覆盖了点并计算其面积。没有必要以任何方式对它们进行预处理，因为您只需要回答一个问题。
只有在将来需要回答许多类似的问题时，预处理才有意义。
当然，您确实需要至少处理一次所有矩形。但是明智地使用第一次传递，您可以在以后获得多个更快的查找。
我会将矩形插入到K-d树或四叉树中。
如果将同一矩形集与许多点查询一起使用，则 R 树数据结构允许知道哪些矩形包含给定的点，而无需检查所有矩形
-
我有一个图像，我想在鼠标移动到某些矩形区域时显示工具提示。矩形区域可以达到1000。但是，只要检查每个矩形中的点是否在其中，即O（N），就会使界面在移动鼠标时没有响应。 有没有小于O(N)的方法？我可以预先对矩形进行排序(我假设这是必需的)。矩形可能会(很少)重叠，但同一区域重叠的矩形不能超过4-5个。在这种情况下，我可能需要获得所有矩形的列表，但即使只是其中的任何一个也足够了。 但是我假设这个问
-
这应该是正确的：
-
我正在做一个与计算几何有关的个人项目。标题中的问题是对一个小子问题的抽象，我正在努力，但正在努力有效地解决。希望它足够普遍，也许不仅仅是我！ 想象一下，我们在平面中有一组S矩形，所有这些矩形的边都平行于坐标轴（没有旋转）。对于我的问题，我们假设矩形交集非常普遍。但它们也非常好：如果两个矩形相交，我们可以假设其中一个总是完全包含另一个。因此，没有“部分”重叠。 我想以以下方式存储这些矩形： 我们可以
-
这是一个面试问题。 我们被赋予各种矩形的尺寸，我们必须找出可以包围所有矩形的矩形面积（最小值）？矩形也可以旋转。 在将矩形拟合到最小可能区域之前，我曾问过一个类似的问题。 上述方法考虑了所有可能性、旋转，并在所有布局情况下确定了所有此类可能性的最小值<我们不能先求矩形面积之和，然后再求最大长度、最大宽度吗？
-
给定一个整数数组，其中每个元素表示可以从该元素向前执行的最大步数。编写一个函数，返回到达数组末尾（从第一个元素开始）的最小跳转次数。如果元素为0，则无法在该元素中移动。 输入： arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} 输出： 3（1- 发现了从动态规划方法到其他线性方法的多种方法。我无法理解所谓的时间线性方法。这里是一个链接，其中提出了一种线性方法。
-
我正在寻找一个算法来查找并打印给定圆的交点。每个圆由其中心和半径指定。 O(n2)算法包括检查中心之间的距离是否小于或等于（被比较的两个圆的）半径之和。然而，我正在寻找一个更快的！ 一个类似的问题是线段的相交。我想即使我的问题可以解决使用行扫描算法，但我无法弄清楚如何修改事件队列在情况下的圆。