解题思路

本题要求找到包含至少 ( C ) 片三叶草田的最小正方形畜栏边长，正方形边平行于坐标轴。通过离散化坐标、二维前缀和与二分查找实现高效求解，步骤如下：

1. 坐标离散化

由于坐标范围大（( 1 \leq X, Y \leq 10^4 )），直接处理不现实。将所有三叶草田的 ( X ) 和 ( Y ) 坐标提取后排序去重，映射到连续整数区间，压缩数据规模。

2. 二维前缀和数组

构建离散化后的二维前缀和数组 maze，其中 maze[i][j] 表示离散化坐标 (xx[i], yy[j]) 左上方区域的三叶草田总数。利用前缀和公式 ( maze[i][j] = maze[i-1][j] + maze[i][j-1] - maze[i-1][j-1] + \text{当前点数量} ) 快速计算任意矩形区域内的三叶草田数量。

3. 二分查找最小边长

通过二分法枚举可能的边长 mid，判断是否存在边长为 mid 的正方形满足条件：

• 对每个 mid，枚举右边界 ( x2 ) 和 ( y2 )，用双指针确定左边界 ( x1 ) 和 ( y1 )，确保横向和纵向长度均 ≤ mid。
• 利用前缀和计算矩形区域内的三叶草田数量，若 ≥ ( C )，则 mid 可行，尝试更小边长；否则增大边长。

代码实现

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
using namespace std;
  
typedef long long LL;
  
const int inf=0x3f3f3f3f;
 
const int N=550;
 
int c,n;
 
struct Pos
{
	int x,y;
	void input()
	{
		scanf("%d%d",&x,&y);
	}
}point[N];
 
vector<int>xx,yy;
 
int maze[N][N];
 
int get_id(vector<int>&v,int x)//离散化映射 
{
	return lower_bound(v.begin(),v.end(),x)-v.begin();
}
 
void disc(vector<int>&v)//离散化 
{
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
}
 
bool check(int mid)
{
	for(int x1=1,x2=1;x2<=xx.size();x2++)//枚举x2，放缩x1
	{
		while(xx[x2]-xx[x1]+1>mid)
			x1++;
		for(int y1=1,y2=1;y2<=yy.size();y2++)//枚举y2，放缩y1
		{
			while(yy[y2]-yy[y1]+1>mid)
				y1++;
			if(maze[x2][y2]-maze[x2][y1-1]-maze[x1-1][y2]+maze[x1-1][y1-1]>=c)//只要存在一个区间满足条件直接返回
				return true;
		} 
	}
	return false;
}
 
int main()
{
//  freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	scanf("%d%d",&c,&n);
	xx.push_back(0);//记得前置一个0
	yy.push_back(0); 
	for(int i=1;i<=n;i++)//读入坐标
	{
		point[i].input();
		xx.push_back(point[i].x);
		yy.push_back(point[i].y);
	}
	disc(xx);//分别离散化
	disc(yy);
 	for(int i=1;i<=n;i++)//维护离散化后的前缀和
 		maze[get_id(xx,point[i].x)][get_id(yy,point[i].y)]++;
	for(int i=1;i<=xx.size();i++)//同上
		for(int j=1;j<=yy.size();j++)
			maze[i][j]+=maze[i-1][j]+maze[i][j-1]-maze[i-1][j-1];
	int l=1,r=inf;
	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;
}

代码说明

• 离散化处理：disc 函数排序去重，get_id 函数通过二分查找获取坐标索引。
• 前缀和构建：统计每个离散化点的三叶草数量，再计算二维前缀和。
• 二分查找：check 函数用双指针枚举区间，利用前缀和快速判断是否存在合法正方形，逐步缩小边长范围，最终输出最小边长。

此代码通过离散化和二分查找优化，高效解决了大范围坐标下的最小正方形问题。