题目描述

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

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

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

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

输入输出格式

输入格式：

第一行两个数C和n。

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

输出格式：

一个数表示答案。

 

输入输出样例

输入样例#1：

3 41 22 14 15 2

输出样例#1：

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

说明

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

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

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

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

 

1 /* 2 如果边长为x可行，边长x+1也一定能覆盖至少C个糖果 3 假如x不可行，边长为x-1是不可能覆盖C个糖果的。 ——> 二分答案。 4 l=1,r=10000,  判断mid是否可行，  可行->  答案在[l,mid] ，不可行 -> (mid,r] 5 while (l<=r) {if (!check((l+r)/2)) l=(l+r)/2+1; else r=(l+r)/2-1;} 6 二分完答案后，怎么判定。 7 ↓↓↓↓↓↓↓↓↓↓↓ 8 枚举上边在哪里。 9 下边的位置是固定的。10 哪些糖果被夹在这段区间中。 O(n)11 12 左边为1的情况下，右边是什么13 随着左边向右移动，右边也一定向右移动。14 左边至多移动n次，右边也至多移动n次，总共2n次。  O(n)15 */16 17 #include
      
       18 #include
       
        19 #include
        
         20 #include
         
          21 #include
          
           22 using namespace std;23 24 int C,n,L,R,mid,temp[1005];25 struct Candy26 {27     int x,y;28     bool operator < (Candy a) const        //在结构体里一定要写const29     {30         return x
           
            x) //边长比二分的边长大了 54 {55 if(judge(l,i-1)) return true; //判断是否可行，i-1是因为要找的边长<=mid 56 while(candy[i].x-candy[l].x>x) l++; //不行的话，左边界向右移动 57 }58 }59 if(judge(l,n)) return true; //单独判断n为右边界的时候是否可行，因为r==n时没法在上面的for循环中写 60 return false;61 }62 63 int main()64 {65 scanf("%d%d",&C,&n);66 for(int i=1;i<=n;i++)67 {68 scanf("%d%d",&candy[i].x,&candy[i].y);69 }70 sort(candy+1,candy+n+1);71 L=1,R=10000;72 while(L<=R) //二分一个边长 73 {74 mid=(L+R)>>1;75 if(check(mid)) R=mid-1;76 else L=mid+1;77 }78 printf("%d",L+1);79 return 0;80 }