问正确性
查看原帖
问正确性
305735
Jean_Gunnhildr楼主2024/11/25 21:28

都说要什么“从左往右扫一遍,再从右边往左扫一遍”,我寻思也不用啊,我就把矩形四个角也当作障碍点,然后扫了一便,再考虑一下特殊情况,就过了···求大佬解答我的算法是否正确

#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;
}

2024/11/25 21:28
加载中...