# 分治 | [USACO06JAN]把牛Corral the Cows

## Desciption

Farmer John wishes to build a corral for his cows. Being finicky beasts, they demand that the corral be square and that the corral contain at least C (1 <= C <= 500) clover fields for afternoon treats. The corral’s edges must be parallel to the X,Y axes.

FJ’s land contains a total of N (C <= N <= 500) clover fields, each a block of size 1 x 1 and located at with its lower left corner at integer X and Y coordinates each in the range 1..10,000. Sometimes more than one clover field grows at the same location; such a field would have its location appear twice (or more) in the input. A corral surrounds a clover field if the field is entirely located inside the corral’s borders.

Help FJ by telling him the side length of the smallest square containing C clover fields.

## Input

Line 1: Two space-separated integers: C and N

Lines 2..N+1: Each line contains two space-separated integers that are the X,Y coordinates of a clover field.

## Output

Line 1: A single line with a single integer that is length of one edge of the minimum size square that contains at least C clover fields.

## Sample Input

3 4
1 2
2 1
4 1
5 2


## Sample Output

4


## Hint

Explanation of the sample:

 * *
 * *

+——Below is one 4x4 solution (C’s show most of the corral’s area); many others exist.

 CCCC
 CCCC
 CCC
 CC

+——

## Codes

#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 10001
#define fr(na,st,ed) for(int na=st;na<=ed;na++)
using namespace std;
int x[maxn],y[maxn];
int id1[maxn],id2[maxn];
int n,c; int l=1,r,mid;
inline bool cmp1(int q,int w){
return x[q]<x[w];
}
inline bool cmp2(int q,int w){
return y[q]<y[w];
}

inline bool check(int size){
int st,ed,k,sum;
fr(i,1,n){
k=1; sum=0;
st=x[id1[i]]; ed=st+size-1;
fr(j,1,n){
while(y[id2[k]]-y[id2[j]]+1<=size && k<=n){
if(st<=x[id2[k]] && x[id2[k]]<=ed) sum++;
k++;
}
if(sum>=c) return true;
if(st<=x[id2[j]] && x[id2[j]]<=ed) sum--;
}
}
return false;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("t3.in","r",stdin);
freopen("t3.out","w",stdout);
#endif
cin>>c>>n;
fr(i,1,n){
cin>>x[i]>>y[i];
r=max(r,max(x[i],y[i]));
id1[i]=id2[i]=i;
}
sort(id1+1,id1+n+1,cmp1);
sort(id2+1,id2+n+1,cmp2);
while(l<=r){
mid=(l+r)>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
cout<<l;
return 0;
}