题目描述

约翰打算建一个围栏来圈养他的奶牛.作为最挑剔的兽类，奶牛们要求这个围栏必须是正方 形的，而且围栏里至少要有C< 500)个草场，来供应她们的午餐.

约翰的土地上共有C<=N<=500)个草场，每个草场在一块1x1的方格内，而且这个方格的 坐标不会超过10000.有时候，会有多个草场在同一个方格内，那他们的坐标就会相同.

告诉约翰，最小的围栏的边长是多少？

输入输出格式

输入格式：

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.

输出格式：

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.

输入输出样例

输入样例#1：

3 4

1 2

2 1

4 1

5 2

输出样例#1：

4

说明

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*

+——

【题解】

咦，我竟然是0ms跑过的最优解。。。那就发个题解总结一下。

二维双指针法的完美结合

双指针法就是令l=1，从1到n枚举右指针r，然后始终保证[l,r]的区间是满足题目要求的区间，不满足就使l++，并每次用[l,r]更新答案（感觉就是简化的单调队列）

如果坐标都是一维的，我们只用双指针法就能搞定，但是由于是二维的，所以我们要用两重双指针法（四指针法。。。）

先二分答案，分别用双指针法维护纵坐标和横坐标，具体还是看代码吧~

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

#define re register

#define il inline

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

int n,m,nx,ny;

struct field

{

    int x,y;

}p[505];

int rx[505],ry[505],s[505];

il bool cmp1(field a,field b)

{

    return a.x<b.x;

}

il bool cmp2(field a,field b)

{

    return a.y<b.y;

}

il bool solve(int ml)

{

    int i,a,b,c,d,sc,sd;

    a=b=0;

    memset(s,0,sizeof(s));

    while(b<n&&rx[p[b+1].x]-rx[1]+1<=ml) s[p[++b].y]++;

    for(;b<=n;s[p[++b].y]++)

    {

        while(rx[p[b].x]-rx[p[a+1].x]+1>ml) s[p[++a].y]--;

        c=d=sc=sd=0;

        while(d<ny&&ry[d+1]-ry[1]+1<=ml) sd+=s[++d];

        for(;d<=ny;sd+=s[++d])

        {

            while(ry[d]-ry[c+1]+1>ml) sc+=s[++c];

            if(sd-sc>=m) return 1;

        }

    }

    return 0;

}

il int gi()

{

  re int x=0;

  re short int t=1;

  re char ch=getchar();

  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

int main()

{

    m=gi();n=gi();

    rx[0]=ry[0]=-1;

    fp(i,1,n) p[i].x=gi(),p[i].y=gi();

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

    fp(i,1,n)

    {

        if(p[i].x>rx[nx]) ry[++ny]=p[i].y;

        p[i].y=ny;

    }

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

    fp(i,1,n)

    {

        if(p[i].x>rx[nx]) rx[++nx]=p[i].x;

        p[i].x=nx;

    }

    int l=1,r=max(rx[nx],ry[ny]),mid;

    while(l<r)

    {

        mid=(l+r)>>1;

        if(solve(mid)) r=mid;

        else l=mid+1;

    }

    printf("%d",r);

    return 0;

}