洛谷 P1578 奶牛浴场 —— 最大子矩形

题目：https://www.luogu.org/problemnew/show/P1578

枚举左边界，向右枚举右边界，同时不断限制上下边界，最后右边界是整个图的边界；

由于没有做左边界是整个图的边界的情况，所以再从右往左做一遍；

还没有做左右边界都是整个图的边界的情况，所以再特殊做一下；

注意题目上说的是障碍点可以在边界上！

而且不是格子图！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int const xn=;

int n;

struct N{int x,y;}p[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

bool cmp(N a,N b){return a.x<b.x;}

bool cmp2(N a,N b){return a.y<b.y;}

int main()

{

  int L=rd(),W=rd(); n=rd();

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

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

  int ans=,j;

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

    {

      int x=p[i].x,y=p[i].y,l=,r=W;

      for(j=i+;j<=n;j++)

    {

      int nx=p[j].x,ny=p[j].y;

      if(nx==x)continue;

      ans=max(ans,(nx-x)*(r-l));//

      if(ny<y)l=max(l,ny);

      else if(ny>y)r=min(r,ny);

      else break;

    }

      if(j==n+)ans=max(ans,(L-x)*(r-l));

    }

  for(int i=n;i;i--)

    {

      int x=p[i].x,y=p[i].y,l=,r=W;

      for(j=i-;j;j--)

    {

      int nx=p[j].x,ny=p[j].y;

      if(nx==x)continue;

      ans=max(ans,(x-nx)*(r-l));//

      if(ny<y)l=max(l,ny);

      else if(ny>y)r=min(r,ny);

      else break;

    }

      if(j==)ans=max(ans,x*(r-l));

    }

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

  int pre=;

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

    {

      ans=max(ans,L*(p[i].y-pre));

      pre=p[i].y;

    }

  ans=max(ans,L*(W-pre));

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

  return ;

}