我代码把从右向左扫描的部分注释掉了,但是还是ac了,为啥呀。
我又把了别人的代码删掉从右向左,结果wa了。 现在我不太懂为什么要两个方向都扫一遍了。。
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=3e4+5;
struct Node{
int x,y;
}a[N];
bool cmp(Node a,Node b){//按横坐标从小到大排序
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
bool cmp2(Node a,Node b){//按纵坐标从小到大排序
return a.y<b.y;
}
signed main(){
int R,C;
scanf("%d%d",&R,&C);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
}
//将整个大矩形的四个端点加入,视为障碍点
a[++n]={0,0};//
a[++n]={0,C};
a[++n]={R,0};
a[++n]={R,C};
//
sort(a+1,a+1+n,cmp);
//左上角为(0,0),右下角为(R,C)
int ans=0;
for(int i=1;i<=n;i++){//枚举一个边界
int up=C,down=0;
for(int j=i+1;j<=n;j++){//从左往右枚举右边界
ans=max(ans,(a[j].x-a[i].x)*(up-down));
if(a[j].y>a[i].y)up=min(up,a[j].y);
else down=max(down,a[j].y);
}
}
// for(int i=1;i<=n;i++){
// int up=C,down=0;
// for(int j=i-1;j>=1;j--){//从右往左枚举左边界
// ans=max(ans,(a[i].x-a[j].x)*(up-down));
// if(a[j].y>a[i].y)up=min(up,a[j].y);
// else down=max(down,a[j].y);
// }
// }
sort(a+1,a+1+n,cmp2);
for(int i=2;i<=n;i++){
ans=max(ans,(a[i].y-a[i-1].y)*C);
}
printf("%d\n",ans);
return 0;
}
/*
*/