【DP悬线法】奶牛浴场

虽然还是悬线法，但是这道题可不能轻易地套模板了，而是要换一种思路，横着扫一遍，竖着扫一遍，时间复杂度依旧是O(n^2),然而空间复杂度有一定的优化

如果用原来的方法，显然时间空间都会炸（如果你想用map我也没办法...时间换空间？）

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#define st short int

using namespace std;

inline int read(){

    char chr=getchar();    int f=,ans=;

    while(!isdigit(chr)) {if(chr=='-') f=-;chr=getchar();}

    while(isdigit(chr))  {ans=(ans<<)+(ans<<);ans+=chr-'';chr=getchar();}

    return ans*f;

}

void write(int x){

    if(x<) putchar('-'),x=-x;

    if(x>) write(x/);

    putchar(x%+'');

}

struct P{int x,y;}a[];

int L,W,n,x,y,ans;

bool cmp1(const P &x,const P &y){return x.x<y.x||x.x==y.x&&x.y<y.y;}

bool cmp2(const P &x,const P &y){return x.y<y.y||x.y==y.y&&x.x<y.x;}

int main(){

    L=read(),W=read(),n=read();

    for(int i=;i<=n;i++)x=read(),y=read(),a[i]=(P){x,y};

    a[++n]=(P){,},a[++n]=(P){,W},a[++n]=(P){L,},a[++n]=(P){L,W};

    sort(a+,a+n+,cmp1);

    for(int i=;i<=n;i++){

        int le=,ri=W,cnt=i;

        while(a[i].x==a[cnt].x) cnt++;

        int j=cnt;

        while(j<=n){

            ans=max(ans,(a[j].x-a[i].x)*(ri-le));

            if(a[j].y<=a[i].y) le=max(le,a[j].y);

            else ri=min(ri,a[j].y);

            ++j;

        }le=,ri=W,j=cnt;

        while(j<=n){

            ans=max(ans,(a[j].x-a[i].x)*(ri-le));

            if(a[j].y<a[i].y) le=max(le,a[j].y);

            else ri=min(ri,a[j].y);

            ++j;

        }

    }sort(a+,a+n+,cmp2);

    for(int i=;i<=n;i++){

        int le=,ri=L,cnt=i;

        while(a[i].y==a[cnt].y) cnt++;

        int j=cnt;

        while(j<=n){

            ans=max(ans,(a[j].y-a[i].y)*(ri-le));

            if(a[j].x<=a[i].x) le=max(le,a[j].x);

            else ri=min(ri,a[j].x);

            ++j;

        }le=,ri=L,j=cnt;

        while(j<=n){

            ans=max(ans,(a[j].y-a[i].y)*(ri-le));

            if(a[j].x<a[i].x) le=max(le,a[j].x);

            else ri=min(ri,a[j].x);

            ++j;

        }

    }cout<<ans;

    return ;

}