记录编号	124489	评测结果	AAAAAAAAAA
题目名称	[WC 2002] 奶牛浴场	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.460 s
提交时间	2014-10-04 11:24:57	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=5010;
class POINT{
public:
	int x,y;
};
bool operator < (POINT a,POINT b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}
int N,L,W;//障碍数,长,宽
POINT P[SIZEN];
vector<int> Y;
int calc(void){//要求P已按照从左到右,从上到下排序
	int ans=0;
	for(int i=1;i<=N;i++){//现在求左边界上有i的
		int U=W,D=0;//最初,上限是U,下限是D
		for(int j=i+1;j<=N;j++){
			if(P[j].x==P[i].x) continue;
			ans=max(ans,(P[j].x-P[i].x)*(U-D));//计算了被这个点卡住的最大矩形
			//下面该用这个点限限制U和D
			if(P[j].y>=P[i].y) U=min(U,P[j].y);
			else D=max(D,P[j].y);
		}
		ans=max(ans,(L-P[i].x)*(U-D));
	}
	return ans;
}
void work(void){
	int ans=0;
	sort(Y.begin(),Y.end());
	for(int i=1;i<Y.size();i++) ans=max(ans,(Y[i]-Y[i-1])*L);//顶住左右边
	sort(P+1,P+1+N);
	ans=max(ans,calc());//左边界被障碍卡住
	for(int i=1;i<=N;i++) P[i].x=L-P[i].x;
	sort(P+1,P+1+N);
	ans=max(ans,calc());//右边界被障碍卡住
	printf("%d\n",ans);
}
void read(void){
	scanf("%d%d",&L,&W);
	scanf("%d",&N);
	Y.push_back(0);
	for(int i=1;i<=N;i++){
		scanf("%d%d",&P[i].x,&P[i].y);
		Y.push_back(P[i].y);
	}
	Y.push_back(W);
}
int main(){
	freopen("wc2002_happy.in","r",stdin);
	freopen("wc2002_happy.out","w",stdout);
	read();
	work();
	return 0;
}