农夫约翰希望为他的奶牛们建立一个畜栏。
这些挑剔的畜生要求畜栏必须是正方形的,而且至少要包含 CC 单位的三叶草,来当做它们的下午茶。
畜栏的边缘必须与 X,YX,Y 轴平行。
约翰的土地里一共包含 NN 单位的三叶草,每单位三叶草位于一个 1×11×1 的土地区域内,区域位置由其左下角坐标表示,并且区域左下角的 X,YX,Y 坐标都为整数,范围在 11 到 1000010000 以内。
多个单位的三叶草可能会位于同一个 1×11×1 的区域内,因为这个原因,在接下来的输入中,同一个区域坐标可能出现多次。
只有一个区域完全位于修好的畜栏之中,才认为这个区域内的三叶草在畜栏之中。
请你帮约翰计算一下,能包含至少 CC 单位面积三叶草的情况下,畜栏的最小边长是多少。
输入格式
第一行输入两个整数 CC 和 NN。
接下来 NN 行,每行输入两个整数 XX 和 YY,代表三叶草所在的区域的 X,YX,Y 坐标。
同一行数据用空格隔开。
输出格式
输出一个整数,代表畜栏的最小边长。
数据范围
1≤C≤5001≤C≤500,
C≤N≤500C≤N≤500
输入样例:
3 4 1 2 2 1 4 1 5 2
输出样例:
4
代码如下:
#includeusing namespace std; const int N=510; int n,m,c,i,j,k; pair a[N]; inline int check(int now)//双指针判定:大致就是,我们有一个指针i和一个指针j,他们两个负责记录,满足条件的区间的左端点,和右端点. //我们这里显然就是要,检测x坐标在指定区域,y坐标在指定区域. { for(int i=1;i<=n;i++) { int j=0; while(j<=n && a[j].first-a[i].first<=now) //x坐标在指定区域 j++; j--; if (j-i+1 =l && a[u].second<=r) ans++; if (ans>=c) return true; } } return false; } int main() { cin>>c>>n; for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second; sort(a+1,a+1+n);//按照x坐标从小到大的顺序排列,x相同时按照由y坐标从小到大的方式排序 int l=0,r=10000; while(l >1; if (check(mid-1)) r=mid; else l=mid+1; } cout<



