线段树+扫描线
矩形面积并
之前写过矩形周长并
还是跟矩形周长并一样,将每一个矩形的横边和竖边处理出来
用竖边将整个平面分成若干个区间
用线段树维护这些区间被覆盖的长度
再用一条扫描线不断从下往上扫描,扫描横边
当扫描到一个矩形的下边时,将这一段区间在线段树上覆盖掉,更新信息
当扫描到一个矩形的上边时,将这一段区间的覆盖去掉即可
那么只有统计答案时与矩形周长并不同
答案就是当前整个区间被覆盖的长度*两次扫描线的高度之差
#include <iostream> #include <algorithm> #include <map> #include <cstdio> #define inf (int)1e9 using namespace std; int n,w,last,tot,k; double c[10000],ans; double s[10000]; map <double,int> id; struct node { double a,b,c,d; }p[5100]; struct tree { int l,r,sum; double len; }sh[100000]; struct edge { int l,r,kind; double num; }a[11000]; bool cmp(edge a,edge b) { return (a.num<b.num || (a.num==b.num && a.kind>b.kind)); } void pushup(int x) { if (sh[x].sum>0) sh[x].len=c[sh[x].r+1]-c[sh[x].l];//完全覆盖 else if (sh[x].l==sh[x].r) sh[x].len=0;//叶子结点 else sh[x].len=sh[x+x].len+sh[x+x+1].len;//一般情况 } void build(int x,int ll,int rr) { sh[x].l=ll; sh[x].r=rr; sh[x].sum=0; sh[x].len=0; if (ll==rr) return; int mid; mid=(ll+rr)>>1; build(x+x,ll,mid); build(x+x+1,mid+1,rr); } void change(int x,int ll,int rr,int v) { if (sh[x].l>=ll && sh[x].r<=rr) { sh[x].sum+=v; pushup(x); return; } int mid; mid=(sh[x].l+sh[x].r)>>1; if (ll<=mid) change(x+x,ll,rr,v); if (rr>mid) change(x+x+1,ll,rr,v); pushup(x); } int main() { while (1) { tot++; scanf("%d",&n); if (n==0) break; for (int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&p[i].a,&p[i].b,&p[i].c,&p[i].d); k=0; for (int i=1;i<=n;i++) { k++; s[k]=p[i].a; k++; s[k]=p[i].c; } sort(s+1,s+1+k); int m=unique(s+1,s+1+k)-s-1; for (int i=1;i<=m;i++) id[s[i]]=i,c[i]=s[i]; w=0; for (int i=1;i<=n;i++)//处理扫描线 { w++; a[w].l=id[p[i].a];a[w].r=id[p[i].c]; a[w].num=p[i].b;a[w].kind=1; w++; a[w].l=id[p[i].a];a[w].r=id[p[i].c]; a[w].num=p[i].d;a[w].kind=-1; } build(1,0,m+1); sort(a+1,a+1+w,cmp); ans=0; for (int i=1;i<=w;i++) { change(1,a[i].l,a[i].r-1,a[i].kind); if (i==w) break; ans+=(a[i+1].num-a[i].num)*sh[1].len;//统计答案 } printf("Test case #%d\n",tot); printf("Total explored area: %.2f\n\n",ans); } }