原来的题解误导了好多人。
hack数据有一个就是专门针对原来的题解的。

原来题解有两个地方：

1
2
3
4
1 if(q[j].r<=r && q[j].r>=l)

2 if (a[j].y>a[i].y)r=min(r,a[j].y);
            else l=max(l,a[j].y);

乍一看是没什么问题

但是
比如这么一组数据

6 4

4

1 2

4 1

4 3

2 1

画图后大概是这个样子

然后进行模拟，发现有了if输出9

然而实际最大的矩形面积是10

就像这张图，(4,3)这个点就被漏了，所以输出了9

因此只需要把这个错误的剪枝删去即可。

这种问题第一篇题解就有。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<头文件自己想>

using namespace std;

int n,m,s;

struct que{
	int x,y;
}q[10010];

int cmp1(que a,que b)
{
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

int cmp2(que a,que b)
{
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}

int main()
{
	int i,j;
	scanf("%d %d",&n,&m);
	scanf("%d",&s);
	for(i=1;i<=s;i++)
	{
		scanf("%d %d",&q[i].x,&q[i].y);
	}
	q[++s].x=0;
	q[++s].x=n,q[s].y=0;
	q[++s].x=0,q[s].y=m;
	q[++s].x=n,q[s].y=m;
	int ans=0;  //加上四个边界，不用在dp特判边界情况
	sort(q+1,q+s+1,cmp1);//从左到右排序
	for(i=1;i<=s;i++)
	{
		int r=m,l=0,h=n-q[i].x;
		for(j=i+1;j<=s;j++)
		{
				if(h*(r-l)<=ans) break;
				ans=max(ans,(q[j].x-q[i].x)*(r-l));
				if(q[i].y==q[j].y) break;
				if(q[j].y>q[i].y) r=min(r,q[j].y);
				if(q[j].y<q[i].y) l=max(l,q[j].y);
		}
		r=m,l=0,h=q[i].x;
		for(j=i-1;j>=1;j--)
		{
				if(h*(r-l)<=ans) break;
				ans=max(ans,(q[i].x-q[j].x)*(r-l));
				if(q[i].y==q[j].y) break;
				if(q[j].y>q[i].y) r=min(r,q[j].y);
				if(q[j].y<q[i].y) l=max(l,q[j].y);
		}
	}
	sort(q+1,q+s+1,cmp2);  //从右向左在排序，不用向第一个dp那样的原因是已经覆盖了原来左右边界在矩形边上的情况
	for(i=1;i<s;i++) ans=max(ans,(q[i+1].y-q[i].y)*n);
	printf("%d",ans);
	return 0;
}