线段树区间交-杭电1255

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define maxn 10010 struct node { double x1,x2,y; int cover; node(double x1=0,double x2=0,double y=0,int cover=0):x1(x1),x2(x2),y(y),cover(cover){} bool friend operator<(node X,node Y) //排序 { return X.y<Y.y; } }p[maxn]; double sum[maxn<<2]; double sum1[maxn<<2]; int col[maxn<<2]; double x[maxn<<1]; void up(int rt,int l,int r) { if(col[rt]>=2) { sum[rt]=x[r]-x[l-1]; //通过一个点来表示一段区间 ，整段覆盖住了的话，那么长度为右减左 } else if(col[rt]==1) //分类讨论 { sum1[rt]=x[r]-x[l-1]; if(l==r) { sum[rt]=0; } else sum[rt]=sum1[rt<<1]+sum1[rt<<1|1]; } else { sum1[rt]=sum1[rt<<1]+sum1[rt<<1|1]; if(l==r) { sum[rt]=0; } else { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } } } void build(int L,int R,int rt) { col[rt]=0; if(L==R) { sum[rt]=0; sum1[rt]=0; return; } int m=(L+R)/2; build(L,m,rt<<1); build(m+1,R,rt<<1|1); up(rt,L,R); } void update(int L,int R,int rt,int a,int b,int c) { if(a<=L&&b>=R) { col[rt]+=c; up(rt,L,R); return; } int m=(L+R)/2; if(a<=m) { update(L,m,rt<<1,a,b,c); } if(b>m) { update(m+1,R,rt<<1|1,a,b,c); } up(rt,L,R); } int main() { int n,i,len,L,R,Case,T; double x1,x2,y1,y2,S; scanf("%d",&T); while(T--) { scanf("%d",&n); S=0; for(i=0;i<n;i++) { scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); p[2*i]=node(x1,x2,y1,1); p[2*i+1]=node(x1,x2,y2,-1); x[2*i]=x1; //将所有x坐标都放在一个数组里，方便离散化 x[2*i+1]=x2; } memset(sum1,0,sizeof(sum1)); sort(p,p+2*n); //对纵坐标进行排序 sort(x,x+2*n); //离散化第一步，排序的过程 len=unique(x,x+2*n)-x; //离散化第二步，去重的过程 build(1,len,1); //建立树的过程 for(i=0;i<2*n-1;i++) //实际上只用扫描2*n-1条线 { L=lower_bound(x,x+len,p[i].x1)-x+1; //离散化第三步，二分法查找，+1是因为一个点代表一段 R=lower_bound(x,x+len,p[i].x2)-x; //找出上下界 update(1,len,1,L,R,p[i].cover); S+=sum[1]*(p[i+1].y-p[i].y); //sum[1]为当前最大覆盖线段长度 } printf("%.2lf\n",S); } return 0; }