给定一些坐标(x,y)
范围0 < x < 100,000,000和0 < y <100,000 我必须找到最小的方块,其边缘和内部至少包含N个无点.
>我使用向量来存储坐标,并搜索边长为最小长度的所有正方形最大长度maxLength(在相关空间中应用强力)
struct Point
{
int x;
int y;
};
vector<Point> P;
int minLength = sqrt(N) - 1;
int maxLength = 0;
// bigx= largest x coordinate of any point
// bigy= largest y coordinate of any point
// smallx= smallest x coordinate of any point
// smally= smallest y coordinate of any point
(bigx - smallx) < (bigy - smally) ? maxLength = (bigx - smallx) : maxLength = (bigy - smally);
>对于每个平方,我抬起头,穿过完整的向量,看看至少有N个点在它的边缘和内部.
这是相当的时间效率低下.
Q1.我应该使用什么数据结构来提高时间效率而不改变我所使用的算法？
Q2.这个问题的高效算法？
解决方法
接下来要意识到的是,每个点将飞机划分为4个象限,每个象限包含一些点. (当象限有一个像素重叠时,这些可以加起来超过总点数).让我们说,NW(p)是点p的西北点,即具有x> = px和y> = py的点的数量.那么一个正方形的点数是NW(bottomleft)NW(topright) – NW(bottomright) – NW(topleft).
对于所有输入点计算NW(p)是相当容易的.将它们排列为x,并将x乘以y.最西北点有NW(p)== 0.如果是第一点的东南方向,则下一个点可以具有NW(p)== 1,否则它具有NW(p)== 0.在这个阶段跟踪SW(p)也是有用的,因为你在从西到东的点上工作,因此没有从北到南.计算NW(p)后,您可以确定O(1)中的平方S中的点数,
回想一下,方形尺寸受到需要在相对边缘有点的限制.假设点在左边(西部)和右边缘 – 你仍然有按x顺序排列的点.首先假设左边缘位于最左边的x坐标处,并且看到右边缘必须包含N个点.现在将左边缘移动到下一个x坐标,并找到一个新的右边缘(从而新的正方形).这样做直到正方形的右边是最右边的一点.
它也可能是y方向受限.在y方向排列点,重复,然后选择两个结果之间的最小平方.
由于你在x和y方向上线性运行,所以这部分只是O(N),主要因素是O(N log N)排序.
