最模板的扫描线模板题,结果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;
}