您的位置: 首页  >  IT文章  >  P1578 奶牛浴场 有障碍点的最大子矩形

P1578 奶牛浴场 有障碍点的最大子矩形

分类: IT文章 • 2023-11-16 21:53:00

这题咕咕了很久终于写了(QwQ)

思路：扫？

提交：2次

(A)。

题解：

显然能成为答案的矩形的边界一定有障碍点或者与大矩形边界重合。
细节见代码（及注释）

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ull unsigned long long
#define ll long long
#define R register int
using namespace std;
#define pause (for(R i=1;i<=10000000000;++i))
#define In freopen("NOIPAK++.in","r",stdin)
#define Out freopen("out.out","w",stdout)
namespace Fread {
static char B[1<<15],*S=B,*D=B;
#ifndef JACK
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
#endif
inline int g() {
  R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
  if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}
inline void gs(char* s) {
  register char ch; while(isempty(ch=getchar()));
  do *s++=ch; while(!isempty(ch=getchar()));
}
} using Fread::g; using Fread::gs;
namespace Luitaryi {
const int N=5010;
struct node { int x,y;
  inline bool operator <(const node& that) const {return x==that.x?y<that.y:x<that.x;}//按横坐标排序
  inline bool operator >(const node& that) const {return y==that.y?x<that.x:y<that.y;}//按纵坐标排序
}a[N];
int n,m,cnt,ans;
inline void main() {
  n=g(),m=g(),cnt=g();
  for(R i=1;i<=cnt;++i) a[i].x=g(),a[i].y=g();
  a[++cnt].x=0,a[cnt].y=0,a[++cnt].x=n,a[cnt].y=m,
  a[++cnt].x=0,a[cnt].y=m,a[++cnt].x=n,a[cnt].y=0;//把四个角也当做障碍点，为的是考虑与边界重合的情况
  sort(a+1,a+cnt+1);//按横坐标排序
  for(R i=1;i<=cnt;++i) {
    R up=m,dn=0,w=n-a[i].x;//up：上界，dn：下界，w：可以向右延伸的最大宽度
    for(R j=i+1;j<=cnt;++j) {
      if(ans>w*(up-dn)) break;//一个小剪枝
      ans=max(ans,(a[j].x-a[i].x)*(up-dn));
      if(a[i].y==a[j].y) break;//同样高度就不必向右继续扫描
      //（此时矩形已经成为了一条线了，但就算你不把它看成线，过这条线且以a[i]为左边界的子矩形也一定不优（可以往左扩））
      if(a[i].y<a[j].y) up=min(a[j].y,up);//更新上下界
      if(a[i].y>a[j].y) dn=max(a[j].y,dn);
    } up=m,dn=0,w=a[i].x;
    for(R j=i-1;j;--j) {
      if(ans>w*(up-dn)) break;
      ans=max(ans,(a[i].x-a[j].x)*(up-dn));
      if(a[i].y==a[j].y) break;
      if(a[i].y<a[j].y) up=min(a[j].y,up);
      if(a[i].y>a[j].y) dn=max(a[j].y,dn);
    }
  }//此时已经处理完正常情况和与大矩形上下边界重合的情况
  sort(a+1,a+cnt+1,greater<node>());//按纵坐标排序
  for(R i=1;i<cnt;++i) ans=max(ans,(a[i+1].y-a[i].y)*n);//处理与大矩形左右边界重合的情况
  printf("%d
",ans);
}
}
signed main() {
  Luitaryi::main(); return 0;
}

2019.07.23

相关推荐