题目：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\n",ans); return 0; }
原文：https://www.cnblogs.com/Zinn/p/9862238.html