障碍物法求解最大子矩阵
有如下三种情况：
- 左边界必定为障碍物
- 右边界必定为障碍物
- 左右边界为矩形边界
可以加入四个点表示矩形的四个端点，然后按x从小到大排序，第一二种情况就可以 $ O(T^2) $ 枚举出来 第三种情况即按y排序，一长度为x的最大值n，另一长度就是两点y的差值
cpp
void solve(){
int l,w,n;
cin>>l>>w>>n;
vector<PLL> a;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
a.emplace_back(x,y);
}
n+=4;
a.emplace_back(0,0);
a.emplace_back(0,w);
a.emplace_back(l,0);
a.emplace_back(l,w);
sort(a.begin(),a.end(),[&](PLL x,PLL y){
return x.x<y.x;
});
ll ans=0;
for(int i=0;i<n;i++){
ll x1=a[i].x,x2=a[i].x,y1=0,y2=w;
for(int j=i+1;j<n;j++){
x2=a[j].x;
ans=max(ans,(x2-x1)*(y2-y1));
if(a[j].y<a[i].y)y1=max(y1,a[j].y);
else y2=min(y2,a[j].y);
}
x1=a[i].x,x2=a[i].x,y1=0,y2=w;
for(int j=i-1;j>=0;j--){
x2=a[j].x;
ans=max(ans,(x1-x2)*(y2-y1));
if(a[j].y<a[i].y)y1=max(y1,a[j].y);
else y2=min(y2,a[j].y);
}
}
sort(a.begin(),a.end(),[&](PLL x,PLL y){
return x.y<y.y;
});
for(int i=0;i<n-1;i++)ans=max(ans,(a[i+1].y-a[i].y)*l);
cout<<ans;
}