这道题是我在寒假的模拟赛里碰到的，现在想起来仍觉得余味无穷。题目大意大致如下：给你一个矩形并在其中划出一个最大的子矩形，当然，在这个矩形里有些地方是取不到的，也就是说我们划的这个子矩形不能包含这些点（边界除外）。那么由于时间问题，就让我简单的说一下王知昆论文里的第一种算法（论文链接：http://pan.baidu.com/s/1bnAl6O3）。
首先，我们将所有的点按横坐标从小到大排序一下；然后，我们先设置一个上边界(maxy)和一个下边界(miny)（初始值设为矩形的宽和0），再分别以每一个点为左边界从左到右扫一遍，当扫到一个点时若他的y<maxy 则将当前的上边界就更换为他的y(这样的话无论后面怎么扫，这个点都不会跑到矩形里面)，反之如果y>miny,miny=y;或许你现在可能会有疑问了：如果y>=maxy||y<=miny怎么办，其实这个的话就可以直接不鸟它，理由是如果改变了这是的maxy或miny则前面的点就会有些落到矩形内，这显然是不符合题意的。
当从左往右扫完一遍后，我们可以找出以右边界为边的子矩形(当然，这有可能不是最大的),那么对于以左边界为边的子矩形又该怎么办呢......
想必你已经想到了，不就是再从右往左再扫一遍嘛。好了，这样就完美了吗？是的，如果你提交到vijos就能ac了(数据太弱没办法).但如果再考虑一下就会发现还有分别以左右边界为边的子矩形，这个的话再从上往下扫一遍就行了。
代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=+;
struct node
{
int x;
int y;
}p[maxn];
int l,w,n;
int maxy,miny;
int maxans=,s=;
bool comp(node a,node b)
{
return(a.x<b.x);
}
bool comp1(node a,node b)
{
return (a.y>b.y);
}
void qsort(int left,int right)
{
int i=left,j=right;
int mid=p[(left+right)/].x;
while(i<=j)
{
while(p[i].x<mid)
i++;
while(p[j].x>mid)
j--;
if(i<=j)
{
int temp=p[i].x;
p[i].x=p[j].x;
p[j].x=temp;
i++;
j--;
}
}
if(i<right)
qsort(i,right);
if(j>left)
qsort(left,j);
}
int main()
{
// freopen("happy.in","r",stdin);
// freopen("happy.out","w",stdout);
cin>>l>>w;
cin>>n;
if(n==)
{
cout<<l*w<<endl;
return ;
}
for(int i=;i<=n;i++)
cin>>p[i].x>>p[i].y;
sort(p+,p+n+,comp);
// qsort(1,n);
int dx,dy;
for(int i=;i<=n;i++)
{
miny=;
maxy=w;
s=;
for(int j=i+;j<=n;j++)
{
dx=p[j].x-p[i].x;
dy=maxy-miny;
s=dx*dy;
maxans=max(s,maxans);
// if(p[j].y==p[i].y)
// {
// break;
// }
// if(p[j].y>p[i].y&&p[j].y<maxy)
// {
// maxy=p[j].y;
// }
// if(p[j].y<p[i].y&&p[i].y>miny)
// {
// miny=p[j].y;
// }
if(p[j].y>=p[i].y && p[j].y<maxy)
maxy=p[j].y;
if(p[j].y<=p[i].y && p[j].y>miny)
miny=p[j].y;
}
dx=l-p[i].x;
dy=maxy-miny;
s=dx*dy;
maxans=max(s,maxans);
}
for(int i=n;i>=;i--)
{
maxy=w;
miny=;
s=;
for(int j=i-;j>=;j--)
{
dx=p[i].x-p[j].x;
dy=maxy-miny;
s=dx*dy;
maxans=max(s,maxans);
// if(p[i].y==p[j].y)
// {
// break;
// }
// if(p[j].y>p[i].y&&p[j].y<maxy)
// {
// maxy=p[j].y;
// }
// if(p[j].y<p[i].y&&p[j].y>miny)
// {
// miny=p[j].y;
// }
if(p[j].y>=p[i].y && p[j].y<maxy)
maxy=p[j].y;
if(p[j].y<=p[i].y && p[j].y>miny)
miny=p[j].y;
}
dx=p[i].x;
dy=maxy-miny;
s=dx*dy;
maxans=max(s,maxans);
}
sort(p+,p+n+,comp1);
for(int i=;i<=n;i++)
{
if(i==)
{
dy=w-p[i].y;
s=l*dy;
maxans=max(maxans,s);
}
else if(i==n)
{
dy=p[i].y;
s=l*dy;
maxans=max(maxans,s);
}
else
{
dy=p[i-].y-p[i].y;
s=l*dy;
maxans=max(maxans,s);
}
}
cout<<maxans<<endl;
return ;
}