poj3179 Corral the Cows

二分+离散化+前缀和好像过不了。。。就先gu了。

只能拿70分。

#include<bits/stdc++.h>
using namespace std;
vector<int>v;
int get_id(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
int c,n,len,a[1010][1010],x[510],y[510],f[1010][1010];
int get_(int x1,int y1,int x2,int y2){
    return f[x1][y1]-f[x1][y2-1]-f[x2-1][y1]+f[x2-1][y2-1];
}
bool check(int k){
    memset(f,0,sizeof(f));
    for(int i=1;i<=len;++i){
        for(int j=1;j<=len;++j){
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
            if(get_(i,j,max(1,i-k),max(1,j-k))>=c)return 1;
        }
    }
    return 0;
}
int main(){
    freopen("a.txt","r",stdin);
    scanf("%d%d",&c,&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x[i],&y[i]);
        v.push_back(x[i]);
        v.push_back(y[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    len=v.size();
    for(int i=1;i<=n;++i){
        a[get_id(x[i])][get_id(y[i])]++;
    }
    int l=0,r=v.size()-1,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%d",v[ans]);
    return 0;
}