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

---

思路：扫？

提交：2次

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

题解：

显然能成为答案的矩形的边界一定有障碍点或者与大矩形边界重合。

细节见代码（及注释）

#include
    
     #include
     
      #include
      
       #define ull unsigned long long#define ll long long#define R register intusing 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++)#endifinline 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
       
        
         (const node& that) const {return y==that.y?x
         
          
           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) 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) dn=max(a[j].y,dn); } }//此时已经处理完正常情况和与大矩形上下边界重合的情况 sort(a+1,a+cnt+1,greater
             
              ());//按纵坐标排序 for(R i=1;i
             
            
           
          
         
        
       
      
     
    

---

2019.07.23