才初学扫描线，好惭愧，看的这篇博客https://blog.csdn.net/qq_18661257/article/details/47622677
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int maxn=200; double sum[maxn<<2],x[maxn*2]; int lazy[maxn<<2]; struct note { double l,r,h; int ff; note() {} note(double l,double r,double h,int ff):l(l),r(r),h(h),ff(ff) {} bool operator <(const note &p) const { return h<p.h; } }aa[maxn*2]; void pushup(int l,int r,int rt) { if(lazy[rt]) sum[rt]=x[r+1]-x[l];//离散化的应该是线段树上的点 else if(l==r) sum[rt]=0;//叶子节点为0 else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void update(int L,int R,int v,int l,int r,int rt) { if(L<=l&&r<=R) { lazy[rt]+=v;//这里不是懒惰标记，只是单纯flag标记，标记存在，说明它标记的这条线段存在，即是下面怎么更新，sum还是会每次只按自己的x[r+1]-x[l]更新，而不会sum[rt<<1]+sum[rt<<1|1]使用下面的值，这就是为什么线段不会重复加的原因 pushup(l,r,rt); return; } int mid=(l+r)>>1; if(L<=mid) update(L,R,v,l,mid,rt<<1); if(mid<R) update(L,R,v,mid+1,r,rt<<1|1); pushup(l,r,rt); } int n; int main() { int Case=0; while(~scanf("%d",&n)&&n) { memset(sum,0,sizeof(sum)); memset(lazy,0,sizeof(lazy)); double a,b,c,d; int cnt=0; for(int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&a,&b,&c,&d); cnt++; aa[cnt]=note(a,c,b,1); x[cnt]=a; cnt++; aa[cnt]=note(a,c,d,-1); x[cnt]=c; } sort(x+1,x+1+cnt); sort(aa+1,aa+1+cnt); int nn=unique(x+1,x+1+cnt)-(x+1); double ans=0; for(int i=1;i<=cnt;i++) { int l=lower_bound(x+1,x+1+nn,aa[i].l)-x;//离散化 int r=lower_bound(x+1,x+1+nn,aa[i].r)-x; r--; ans+=sum[1]*(aa[i].h-aa[i-1].h);//应该是底乘以高，底是上一次用的线段，所以应该先求和，再更新这次的 update(l,r,aa[i].ff,1,cnt,1); } printf("Test case #%d\nTotal explored area: %.2f\n\n",++Case,ans); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/9428593.html
