题解 P1578 【奶牛浴场】

2018-02-26 16:11:42


https://wenku.baidu.com/view/56f7342b3169a4517723a3ad.html

以上是王知昆大佬写的,解题思路不做赘述。

以下是我的代码

#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;
}