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

这题咕咕了很久终于写了\(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\n",ans);

}

}

signed main() {

  Luitaryi::main(); return 0;

}

2019.07.23

巴特西

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

思路：扫？

提交：2次

错因：数据差评，第一次把矩形的长宽搞反了竟然只有一个点没有\(A\)。

题解：

最新文章

热门文章

巴特西

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

思路：扫？

提交：2次

错因：数据差评，第一次把矩形的长宽搞反了竟然只有一个点没有\(A\)。

题解：

最新文章

热门文章

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