[USACO12FEB]Overplanting S

洛咕

题意：在一个笛卡尔平面坐标系里（X轴向右是正方向，Y轴向上是正方向），有\(N(1<=N<=1000)\)个矩形，第\(i\)个矩形的左上角坐标是\((x1, y1)\),右下角坐标是\(（x2,y2）\)。问这\(N\)个矩形所覆盖的面积是多少？注意：被重复覆盖的区域的面积只算一次。

分析：比较经典的扫描线模板题。对于每个给出的矩形，左边线视为\(+1\)，右边线视为\(-1\)，从左到右扫描，要求每两根相邻的矩形边线贡献的面积，宽度就是两线横坐标之差，长度要用线段树来维护区间加减。本题由于横纵坐标取值范围达到\(10^8\)量级，所以先要离散化处理一下。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline int read(){

    char ch=getchar();int x=0,f=1;

    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

	while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int mod=10007;

const int N=10005;

int n,tot,a[N];

ll raw[N],sum[N<<2],cnt[N<<2];

struct node{int x,y1,y2,z;}e[N];

inline bool cmp(node x,node y){return x.x==y.x?x.y1<y.y1:x.x<y.x;}

inline void change(int p,int l,int r,int ql,int qr,int val){

	if(ql<=l&&qr>=r){

		cnt[p]+=val;

		if(cnt[p]>0)sum[p]=raw[r+1]-raw[l];

		else sum[p]=sum[p<<1]+sum[p<<1|1];

		return;

	}

	int mid=(l+r)>>1;

	if(ql<=mid)change(p<<1,l,mid,ql,qr,val);

	if(qr>mid)change(p<<1|1,mid+1,r,ql,qr,val);

	if(cnt[p]>0)sum[p]=raw[r+1]-raw[l];

	else sum[p]=sum[p<<1]+sum[p<<1|1];

}

int main(){

	n=read();

	for(int i=1;i<=n;++i){

		int x1=read(),y2=read(),x2=read(),y1=read(),k1=(i<<1)-1,k2=i<<1;

		e[k1].x=x1;e[k1].y1=y1;e[k1].y2=y2;e[k1].z=1;

		e[k2].x=x2;e[k2].y1=y1;e[k2].y2=y2;e[k2].z=-1;

		a[++tot]=y1;a[++tot]=y2;

	}

	sort(a+1,a+tot+1);int len=unique(a+1,a+tot+1)-a-1;n<<=1;

	for(int i=1;i<=n;i+=2){

		int pos1=lower_bound(a+1,a+len+1,e[i].y1)-a;

		int pos2=lower_bound(a+1,a+len+1,e[i].y2)-a;

		raw[pos1]=e[i].y1;raw[pos2]=e[i].y2;

		e[i].y1=e[i+1].y1=pos1;e[i].y2=e[i+1].y2=pos2;

	}

	sort(e+1,e+n+1,cmp);ll ans=0;

	for(int i=1;i<=n;++i){

		change(1,1,n,e[i].y1,e[i].y2-1,e[i].z);

		ans+=1ll*(e[i+1].x-e[i].x)*sum[1];

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

[USACO12FEB]Overplanting S

洛咕

最新文章

热门文章