POJ 3179 Corral the Cows

Corral the Cows

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 1352		Accepted: 565

Description

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

Sample Output

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*


|C*C*


+------

Source

USACO 2006 January Gold

题意：需要你搭建一个正方形的围栏，围栏里面需要有至少C个特殊的点，问你正方形最短的边长是多少

题解：给的坐标可能会重复，所以我们按照x坐标的和y坐标从小到大排序后离散化，用二维前缀和记录区域内点的个数，然后二分答案，每次检查时检查区域内的点是否满足大于C个即可

代码如下：

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = ;

int C,n;

struct node{

    int x,y;

}p[maxn];

int xn,yn,rx[maxn],ry[maxn];

int sum[maxn][maxn];

bool cmp1(node a,node b){

    return a.x<b.x;

}

bool cmp2(node a,node b){

    return a.y<b.y;

}

bool check(int k){

    for(int a=,b=;;a++){

        while(rx[b+]-rx[a]+<=k&&b<xn) b++;

        for(int c=,d=;;c++){

            while(ry[d+]-ry[c]+<=k&&d<yn) d++;

            int ans=sum[b][d]+sum[a-][c-]-sum[a-][d]-sum[b][c-];

            if(ans>=C) return true;

            if(d==yn) break;

        }

        if(b==xn) break;

    }

    return false;

}

int main(){

    scanf("%d%d",&C,&n);

    for(int i=;i<=n;i++){

        scanf("%d%d",&p[i].x,&p[i].y);

    }

    sort(p+,p+n+,cmp1);

    xn=;rx[]=p[].x;p[].x=;

    for(int i=;i<=n;i++){

        if(p[i].x!=p[i-].x) rx[++xn]=p[i].x;

        p[i].x=xn;

    }

    sort(p+,p+n+,cmp2);

    yn=;ry[]=p[].y;p[].y=;

    for(int i=;i<=n;i++){

        if(p[i].y!=p[i-].y) ry[++yn]=p[i].y;

        p[i].y=yn;

    }

    for(int i=;i<=n;i++) sum[p[i].x][p[i].y]++;

    for(int i=;i<=xn;i++){

        for(int j=;j<=yn;j++){

            sum[i][j]+=sum[i][j-]+sum[i-][j]-sum[i-][j-];

        }

    }

    int l=,r=max(rx[xn],ry[yn]),ans;

    while(l<=r){

        int mid=l+r>>;

        if(check(mid)){

            ans=mid;

            r=mid-;

        }else{

            l=mid+;

        }

    }

    printf("%d\n",ans);

}

巴特西

POJ 3179 Corral the Cows

最新文章

热门文章