比赛 论文练习 评测结果 AAAAAAAAAA
题目名称 奶牛浴场 最终得分 100
用户昵称 烟雨 运行时间 0.197 s
代码语言 C++ 内存使用 2.00 MiB
提交时间 2018-10-19 20:19:49
显示代码纯文本
#include<cstdio>
#include<algorithm>
#define maxn 5050
using namespace std;
int n,m,k,ans;
struct node
{
	int x,y;
}s[maxn];
int cmp1(node a,node b){return a.x<b.x;}
int cmp2(node a,node b){return a.y<b.y;}
int read()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;++i)
	{
		scanf("%d%d",&s[i].x,&s[i].y);
	}
	s[++k].x=n;
	s[++k].y=m;
	return 0;
}
int work()
{
	int up,down,l;
	sort(s+1,s+k+1,cmp1);
	for(int i=1;i<=k;++i)
	{
		up=0;down=m;l=n-s[i].x;
		for(int j=i+1;j<=k;++j)
		{
			if(s[j].y>=up && s[j].y<=down)
			{
				if(l*(down-up)<=ans)break;
				ans=max(ans,(s[j].x-s[i].x)*(down-up));
				if(s[i].y==s[j].y)break;
				if(s[j].y>s[i].y && s[j].y<down)down=s[j].y;
				if(s[j].y<s[i].y && s[j].y>up)up=s[j].y;
			}
		}
		up=0;down=m;l=n-s[i].x;
		for(int j=i-1;j>=1;--j)
		{
			if(s[j].y>=up && s[j].y<=down)
			{
				if(l*(down-up)<=ans)break;
				ans=max(ans,(s[i].x-s[j].x)*(down-up));
				if(s[i].y==s[j].y)break;
				if(s[j].y>s[i].y && s[j].y<down)down=s[j].y;
				if(s[j].y<s[i].y && s[j].y>up)up=s[j].y;
			}
		}
	}
	sort(s+1,s+k+1,cmp2);
	for(int i=1;i<k;i++)
	{
		ans=max(ans,n*(s[i+1].y-s[i].y));
	}
	printf("%d\n",ans);
	return 0;
}
int main()
{
	freopen ("wc2002_happy.in","r",stdin);
	freopen ("wc2002_happy.out","w",stdout);
	read();
	work();
	return 0;
}