sdut 2401 最大矩形面积

      1http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2401



 /*
最大矩形面积，把边界点加上
从左往右 处理一遍；
再从上往下处理一遍；
*/

#include
#define maxn 20000
#include
#include
using namespace std;
int min(int x,int y)
{
    if(xreturn x;
    else return y;
}
int max(int x,int y)
{
    if(x>y)return x;
    else return y;
}
struct node
{
    int x;
    int y;
}p[maxn];
int n,l,w;
int cmpx(node a,node b)
{
    if(a.x!=b.x)return a.x<b.x;
    else  return a.y<b.y;
}
int cmpy(node a,node b)
{
    if(a.y!=b.y)return a.y<b.y;
    else return a.x<b.x;
}
int LR()
{
    int i,j;
    int top,down;
    int ans=-1;
    for(i=0;i1;i++)
    {
        top=w;down=0;
        for(j=i+1;j)
        {
            if(p[i].x!=p[j].x)
              ans=max(ans,fabs(p[i].x-p[j].x)*(top-down));

              if(p[j].y>p[i].y)top=min(top,p[j].y);
              else
                 down=max(down,p[j].y);
        }
    }
    return ans;
}
int UD()
{
     int i,j;
    int L,R;
    int ans=-1;
    for(i=0;i1;i++)
    {
        L=0;R=l;
        for(j=i+1;j)
        {
            if(p[i].y!=p[j].y)
              ans=max(ans,fabs(p[i].y-p[j].y)*(R-L));

              if(p[j].x>p[i].x)R=min(R,p[j].x);
              else
                 L=max(L,p[j].x);
        }
    }
    return ans;
}
int main()
{
    int T,i;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&l,&w);
        scanf("%d",&n);
        if(n==0)
        {
            printf("%d
",l*w);
            continue;
        }
        p[0].x=0;//加上边界点
        p[0].y=0;
        p[1].x=l;
        p[1].y=w;
        n=n+2;
        for(i=2;i)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
        }
        sort(p,p+n,cmpx);
        int s1=LR();
        sort(p,p+n,cmpy);
        int s2=UD();
        printf("%d
",max(s1,s2));
    }
}