莫名80分
查看原帖
莫名80分
658786
STUDENT00楼主2022/10/9 19:53

最模板的扫描线模板题,结果80分,更加离谱的是我开完O20分!

哪位大佬帮我调调?代码如下:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,in[1010][4],a[2010][2010],ans; 
set<int> sx,sy;
vector<int> xx,yy;
void push(int x1,int y1,int x2,int y2){
	a[x1][y1]++;
	a[x1][y2+1]--;
	a[x2+1][y1]--;
	a[x2+1][y2+1]++;
}
int find(vector<int> a,int b){
	return lower_bound(a.begin(),a.end(),b)-a.begin();
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld",&in[i][0],&in[i][1],&in[i][2],&in[i][3]);
		sx.insert(in[i][0]);
		sx.insert(in[i][2]);
		sy.insert(in[i][1]);
		sy.insert(in[i][3]);
	}
	for(set<int>::iterator it=sx.begin();it!=sx.end();it++) xx.push_back(*it);
	for(set<int>::iterator it=sy.begin();it!=sy.end();it++) yy.push_back(*it);
	for(int i=1;i<=n;i++){
		int x1=in[i][0],y1=in[i][1],x2=in[i][2],y2=in[i][3];
		push(find(xx,x1),find(yy,y1),find(xx,x2)-1,find(yy,y2)-1);
	}
	for(int i=0;i<xx.size();i++){
		for(int j=0;j<yy.size();j++) a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; 
	}
	for(int i=0;i<xx.size()-1;i++){
		for(int j=0;j<yy.size()-1;j++){
			if(a[i][j]) ans+=(xx[i+1]-xx[i])*(yy[j+1]-yy[j]);
		}
	}
	printf("%lld",ans);
	return 0;
}
2022/10/9 19:53
加载中...