题目描述

农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含C单位的三叶草，来当做它们的下午茶。

畜栏的边缘必须与X，Y轴平行。

约翰的土地里一共包含N单位的三叶草，每单位三叶草位于一个1 x 1的土地区域内，区域位置由其左下角坐标表示，并且区域左下角的X,Y坐标都为整数，范围在1到10000以内。

多个单位的三叶草可能会位于同一个1 x 1的区域内，因为这个原因，在接下来的输入中，同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中，才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下，能包含至少C单位面积三叶草的情况下，畜栏的最小边长是多少。

输入格式
第一行输入两个整数 C 和 N。

接下来 N 行，每行输入两个整数 X 和 Y，代表三叶草所在的区域的X,Y坐标。

同一行数据用空格隔开。

样例

输出格式
输出一个整数，代表畜栏的最小边长。

数据范围
1≤C≤500,
C≤N≤500
输入样例：
3 4
1 2
2 1
4 1
5 2
输出样例：
4

算法1

(二维离散化 + 二维前缀和 + 二分) $O(nlogN)$

见代码。。。。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10100 , M = 510;

struct Point{
    int x, y;
}point[N];

int c,n;
int x[N],y[N];
int rx[N],ry[N],tx,ty;
int s[M][M];
bool check(int len){

    for(int i = x[len] ; i <= tx ; i ++)
       for(int j = y[len] ; j <= ty ; j++)
       {
           int x0 = 0 , y0 = 0;
           if(rx[i] - len >= 0)x0 = x[rx[i] - len];
           if(ry[j] - len >= 0)y0 = y[ry[j] - len];
           if(s[i][j] - s[x0][j] - s[i][y0] + s[x0][y0] >= c)return true;
       }
       return false;
}

int main(){

    cin >> c >> n;

    for(int i = 1 ; i <= n ; i++)
    {
        cin >> point[i].x >> point[i].y;
        x[point[i].x]++;
        y[point[i].y]++;
    }

    for(int i = 1 ; i <= 10000 ;i++)
    {
        if(x[i])rx[++tx] = i;
        x[i] = tx;
        if(y[i])ry[++ty] = i;
        y[i] = ty;
    }

    for(int i = 1 ; i <= n ;i++)s[x[point[i].x]][y[point[i].y]]++;
       for (int i = 1; i <= tx; i++)
        for(int j = 1; j <= ty; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + s[i][j];
    int l = 1 , r = 10000;

    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid))r = mid;
        else l = mid + 1;
    }

    cout << r << endl;
    return 0;
}

算法2

(点集+二分) $O(n^2logn)$

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n,c;
struct Point{
    int x,y;

    bool operator<(const Point& w){
        if(x == w.x)return y < w.y;
        return x < w.x;
    }
}point[N];

bool check(int now){

    for(int i = 1 ; i <= n;i++)
    {
        int j = 0;
        while(j <= n && point[j].x - point[i].x <= now)j++;
        j--;


        if(j - i + 1 < c)return false;
        for(int k = i ; k <= j ;k++)
           { int ans = 0;
               int l = point[k].y , r = l + now;
               for(int u = i ; u <= j ;u++)
                  if(point[u].y >= l &&  point[u].y <=r)
                   {
                       ans++;
                       if(ans >= c)return true;
                   }
                    if(ans >= c)return true;
           }
    }
    return false;
}

int main(){

    cin >> c >> n;

    for(int i = 1 ; i <= n ;i++)
    {
        cin >> point[i].x >> point[i].y;
    }
    sort(point + 1 , point + n + 1);

    int l = 1 , r = 1e4 ;

    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid - 1))r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}