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

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

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

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

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

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

而且不是格子图！

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const xn=5005;
int n;
struct N{int x,y;}p[xn];
int rd()
{
  int ret=0,f=1; char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}
  while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',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=1;i<=n;i++)p[i].x=rd(),p[i].y=rd();
  sort(p+1,p+n+1,cmp);
  int ans=0,j;
  for(int i=1;i<=n;i++)
    {
      int x=p[i].x,y=p[i].y,l=0,r=W;
      for(j=i+1;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+1)ans=max(ans,(L-x)*(r-l));
    }
  for(int i=n;i;i--)
    {
      int x=p[i].x,y=p[i].y,l=0,r=W;
      for(j=i-1;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==0)ans=max(ans,x*(r-l));
    }
  sort(p+1,p+n+1,cmp2);
  int pre=0;
  for(int i=1;i<=n;i++)
    {
      ans=max(ans,L*(p[i].y-pre));
      pre=p[i].y;
    }
  ans=max(ans,L*(W-pre));
  printf("%d
",ans);
  return 0;
}