题目描述

在一个10000*10000的二维平面上，有n颗糖果。

LYK喜欢吃糖果！并且它给自己立了规定，一定要吃其中的至少C颗糖果！

事与愿违，LYK只被允许圈出一个正方形，它只能吃在正方形里面的糖果。并且它需要支付正方形边长的价钱。

LYK为了满足自己的求食欲，它不得不花钱来圈一个正方形，但它想花的钱尽可能少，你能帮帮它吗？

输入格式(square.in)

第一行两个数C和n。

接下来n行，每行两个数xi,yi表示糖果的坐标。

输出格式(square.out)

一个数表示答案。

输入样例

3 4

1 2

2 1

4 1

5 2

输出样例

4

样例解释

选择左上角在(1,1)，右下角在(4,4)的正方形，边长为4。

数据范围

对于30%的数据n<=10。

对于50%的数据n<=50。

对于80%的数据n<=300。

对于100%的数据n<=1000。1<=xi,yi<=10000。

分析：一个比较暴力的想法就是枚举边长，然后把所有符合要求的正方形计算一边看看有没有c个,这种做法在枚举边长上花的时间比较多，如果把枚举换成二分就会快很多，而且这道题是满足二分性质的，如果边长x都不能有c个糖果，那么x-1肯定没有c个糖果.二分一下每次检验是否能包含c个糖果即可.

      这个检验比较有技巧性，可以想到的一个方法是前缀和，不过在做前缀和的时候要先离散化.标程给的方法非常好.先固定一个上边界，然后向下扩展，到刚好要超出x的时候把这两个边界中所有的点全部给提取出来，然后考虑左右边界，看第i个和第i+x个的横坐标相差是否≤x.这个方法好在可以很快地枚举出所有符合答案的矩形,也应用了一个思想：想要让(x,y)符合要求，那么先把符合要求的x给提出来，然后看看y是否符合要求.

     存点不要存坐标，这也相当于离散化了坐标.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int c, n, ans, b[1010];struct node{    int x, y;}e[1010];bool cmp(node a, node b){    return a.x < b.x;}bool can(int l, int r, int len){    if (r - l + 1 < c)        return false;    int cnt = 0;    for (int i = l; i <= r; i++)        b[++cnt] = e[i].y;    sort(b + 1, b + 1 + cnt);    for (int i = c; i <= cnt; i++)        if (b[i] - b[i - c + 1] <= len)            return true;    return false;}bool check(int len){    int cur = 1;    for (int i = 1; i <= n; i++)    {        if (e[i].x - e[cur].x > len)        {            if (can(cur, i - 1, len))                return true;        }        while (e[i].x - e[cur].x > len)            cur++;    }    if (can(cur, n, len))        return true;    return false;}int main(){    scanf("%d%d", &c, &n);    for (int i = 1; i <= n; i++)        scanf("%d%d", &e[i].x, &e[i].y);    sort(e + 1, e + 1 + n, cmp);    int l = 0, r = 10000;    while (l <= r)    {        int mid = (l + r) >> 1;        if (check(mid))        {            ans = mid;            r = mid - 1;        }        else            l = mid + 1;    }    printf("%d\n", ans + 1);    return 0;}