mxqz扫描线求周长
查看原帖
mxqz扫描线求周长
324666
diqiuyi奶龙楼主2023/3/31 22:49

rt,WA 了最后两个点

#include <bits/stdc++.h>
using namespace std;
int n,lsy[10005],cnt,cnt2,a,b,c,d,xdt[80005],cover[80005],sum[80005],ans;
bitset<80005> lc,rc;
struct lin{
	int x,y,yy,val;
	bool operator <(lin a) const{
		return (x^a.x)?x<a.x:val>a.val;
	}
}l[10005];
inline void pushup(int p,int lt,int rt){
	if(cover[p]){
		sum[p]=lsy[rt]-lsy[lt],
		xdt[p]=1,lc[p]=rc[p]=1;
		return ;
	}
	sum[p]=sum[p<<1]+sum[p<<1|1],
	xdt[p]=xdt[p<<1]+xdt[p<<1|1],
	lc[p]=lc[p<<1],rc[p]=rc[p<<1|1];
	if(lc[p<<1|1]&&rc[p<<1]) xdt[p]--;
}
void upd(int p,int lt,int rt,int lt2,int rt2,int val){
	if(lt>=lt2&&rt<=rt2){
		cover[p]+=val;
		pushup(p,lt,rt);
		return ;
	}
//	if(rt-lt==1) return ;
	int mid=lt+rt>>1;
	if(lt2<mid) upd(p<<1,lt,mid,lt2,rt2,val);
	if(rt2>mid) upd(p<<1|1,mid,rt,lt2,rt2,val);
	pushup(p,lt,rt);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a>>b>>c>>d,
		l[++cnt]=(lin){a,b,d,1},
		l[++cnt]=(lin){c,b,d,-1},
		lsy[++cnt2]=b,lsy[++cnt2]=d;
	sort(lsy+1,lsy+cnt2+1);
	cnt2=unique(lsy,lsy+cnt2+1)-lsy-1;
	sort(l+1,l+cnt+1);
	for(int i=1,lst=0;i<cnt;i++){
		int ly=lower_bound(lsy,lsy+cnt2+1,l[i].y)-lsy,
		lly=lower_bound(lsy,lsy+cnt2+1,l[i].yy)-lsy;
		upd(1,1,cnt2,ly,lly,l[i].val);
		ans=ans+abs(sum[1]-lst)+2*xdt[1]*(l[i+1].x-l[i].x),lst=sum[1];
 	}
	ans+=l[cnt].yy-l[cnt].y;
	cout<<ans<<'\n';
	return 0;
}
2023/3/31 22:49
加载中...