/* 本题求最小边长，使得最小边长围成的正方形能容纳指定数量的三叶草，首先三叶草的数量不多，但是数据范围很大， 因此第一步可以进行离散化。然后为了方便知道某一个矩形中的三叶草数量，可以采用前缀和的思想，然后要求边长的最小值，求最小值启发我们用二分来做。因此每次二分一个边长 mid，然后枚举图中所有边长为 mid 的正方形，如果存在一个正方形中的三叶草数量满足要求，可以尝试缩小边长，二分左区间。否则二分右区间。枚举过程中用二维前缀和直接线性求三叶草数量即可。 */

#include #include #include

using namespace std;

const int N = 1010; struct node { int x,y; }nodes[10010]; int n, m, k; int s[N][N]; int cnt = 1; int len; int nums[N]; int find(int x) //离散化 { int l = 1, r = cnt-1; while(l < r) { int mid = l + r + 1 >> 1; if(nums[mid] <= x) l = mid; else r = mid - 1; } return r; } bool check(int mid) //判断边长为 mid 是否能包含 m 个三叶草 { for(int x1 = 1, x2 = 1; x2 < cnt; x2++) //枚举横坐标 { while(nums[x2] + 1 - nums[x1] > mid) x1++; for(int y1 = 1, y2 = 1; y2 < cnt; y2++) //枚举纵坐标 { while(nums[y2] + 1 - nums[y1] > mid) y1++; if(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] >= m) return true; } }

return false;

}

int main() { scanf("%d%d", &m, &k); for(int i = 0; i < k; i++) { int x, y; scanf("%d%d", &x, &y); n = max(n, x), n = max(n, y); //记录边界 nums[++len] = x; nums[++len] = y; nodes[i] = (node){x, y}; //存储所有的点 } //坐标离散化 sort(nums + 1, nums + len + 1);

for(int i = 1; i <= len ; i++)
	if(nums[i] != nums[i-1])
		nums[cnt++] = nums[i];

//标记所有位置上的三叶草数量
for(int i = 0; i < k; i++)
{
    int x = find(nodes[i].x), y = find(nodes[i].y);
    s[x][y]++;
}
//初始化前缀和
for(int i = 1; i < cnt; i++)
    for(int j = 1; j < cnt; j++)
        s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
//二分
int l = 1, r = n;
int ans;
while(l <= r)
{
    int mid = l + r >> 1;
    if(check(mid)) 
    {
    	ans = mid;
    	r = mid - 1;
    }
    else l = mid + 1;
}
printf("%d\n", ans);
return 0;

}