c – 用于稀疏数据查找的高效数据结构

给定一些坐标(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.这个问题的高效算法？