都说要什么“从左往右扫一遍,再从右边往左扫一遍”,我寻思也不用啊,我就把矩形四个角也当作障碍点,然后扫了一便,再考虑一下特殊情况,就过了···求大佬解答我的算法是否正确
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=5e3+5;
int n,l,w,ans;
pair<int,int> a[N];
int main(){
set<int> s;
cin>>l>>w>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
s.insert(a[i].y);
}
s.insert(0);s.insert(w);
a[n+1].x=0;a[n+1].y=0;a[n+2].x=0;a[n+2].y=w;a[n+3].x=l;a[n+3].y=0;a[n+4].x=l;a[n+4].y=w;
n+=4;
sort(a+1,a+1+n);
for(int i=1;i<n;i++){
int uplim=w;
int downlim=0;
for(int j=i+1;j<=n;j++){
ans=max(ans,(uplim-downlim)*(a[j].x-a[i].x));
if(a[j].y>a[i].y) uplim=min(uplim,a[j].y);
else downlim=max(downlim,a[j].y);
}
}
int lst=-1,deltamax=0;
while(s.size()){
int tmp=*s.begin();
if(lst==-1) lst=tmp;
else{
deltamax=max(deltamax,tmp-lst);
lst=tmp;
}
s.erase(tmp);
}
ans=max(ans,l*deltamax);
cout<<ans<<endl;
return 0;
}