题解 P1578 【奶牛浴场】

https://wenku.baidu.com/view/56f7342b3169a4517723a3ad.html 以上是王知昆大佬写的，解题思路不做赘述。 以下是我的代码 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,k; int ans=0; struct PPP { int x,y; }p[5100]; bool cmp1(PPP a,PPP b) { return a.x<b.x; } bool cmp2(PPP a,PPP b) { return a.y<b.y; } int main() { freopen("happy.in","r",stdin); freopen("happy.out","w",stdout); scanf("%d%d",&n,&m); scanf("%d",&k); for(int i=1;i<=k;i++) scanf("%d%d",&p[i].x,&p[i].y); sort(p+1,p+k+1,cmp1); ans=max(ans,p[1].x*n);//对边界在矩阵边上的情况进行处理 for(int i=2;i<=k;i++) ans=max(ans,(p[i].x-p[i-1].x)*n); ans=max(ans,(m-p[k].x)*n); sort(p+1,p+k+1,cmp2); for(int i=1;i<=k;i++)//从左往右扫 { int h1=0,h2=m; for(int j=i+1;j<=k;j++) { int s=(h2-h1)*(p[j].y-p[i].y); ans=max(s,ans); if(p[j].x<p[i].x) h1=max(h1,p[j].x); else if(p[j].x==p[i].x) h1=h2=p[i].x; else h2=min(h2,p[j].x); } ans=max(ans,(h2-h1)*(n-p[i].y)); } for(int i=k;i>=1;i--)//从右往左扫 { int h1=0,h2=m; for(int j=i-1;j>=1;j--) { int s=(h2-h1)*(p[i].y-p[j].y); ans=max(s,ans); if(p[j].x<p[i].x) h1=max(h1,p[j].x); else if(p[j].x==p[i].x) h1=h2=p[i].x; else h2=min(h2,p[j].x); } ans=max(ans,(h2-h1)*p[i].y); } cout<<ans; return 0; } ```