赶牛入圈

赶牛入圈

赶牛入圈

有一个(10000times 10000)的网格图，给出n个棋子在网格上的坐标，记第i个棋子的坐标为((x_i,y_i))，现在请求出一个边长最小的正方形（边对齐网格），让其中包含的棋子数大于等于c，(nleq 500)。

解

注意到数字范围很大，数据范围很小，考虑离散化（提一下，网格坐标很小，于是可以桶排排序）。

问题在于离散化后，在离散化后的网格图中我们如何枚举一个正方形，常规思路是确定一个矩形的左上角，再确定右下角，然后对矩形的原始长宽取max就是我们要的正方形边长了，显然时间复杂度太高(O(n^3))。

注意到正方形的顶点都可以是由一个棋子的x轴坐标所确定的直线和另外一个棋子的y轴坐标所确定的直线的交点组成的（不是的也可以平移成如此），我们只要枚举离散化后的x轴坐标和y轴的坐标，即可以确定这个点，然后只要确定对角顶点即可。

但是注意到这个点不一定存在，于是查询出正方形边界的最近的离散化坐标，然后查询这个区间的二维前缀和即可（注意此时的矩形边界上的棋子数要舍区），于是我们就可以在(O(n^2log(n)))解决这道题目。

参考代码：

#include <iostream>
#include <cstdio>
#define il inline
#define ri register
#define intmax 0x7fffffff
using namespace std;
struct pos{int x,y;
}p[550];
int x[10005],y[10005],M[550][550],xl[550],xt,yl[5501],yt,n,c;
il void read(int&);il int check(int);
int main(){read(c),read(n);for(int i(1);i<=n;++i)read(p[i].x),read(p[i].y),++x[p[i].x],++y[p[i].y];for(int i(1);i<=10000;++i){if(x[i])xl[++xt]=i;x[i]=xt;if(y[i])yl[++yt]=i;y[i]=yt;}for(int i(1);i<=n;++i)++M[x[p[i].x]][y[p[i].y]];for(int i(1),j;i<=500;++i)for(j=1;j<=500;++j)M[i][j]+=M[i-1][j]+M[i][j-1]-M[i-1][j-1];int l(1),r(10000),mid;while(l<=r){mid=l+r>>1;if(check(mid))l=mid+1;else r=mid-1;}printf("%d",l);return 0;
}
il int check(int mid){for(int i(x[mid]),j,k,l;i<=xt;++i)for(j=y[mid];j<=yt;++j){k=l=0;if(xl[i]-mid>=0)k=x[xl[i]-mid];if(yl[j]-mid>=0)l=y[yl[j]-mid];if(M[i][j]-M[i][l]-M[k][j]+M[k][l]>=c)return false;}return true;
}
il void read(int &x){x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}

转载于:.html