覆盖的面积
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7985 Accepted Submission(s): 4038
Problem Description
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
Input
输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.
注意:本题的输入数据较多,推荐使用scanf读入数据.
注意:本题的输入数据较多,推荐使用scanf读入数据.
Output
对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.
Sample Input
2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1
Sample Output
7.63 0.00
题目大意：
求n个矩形重复覆盖的面积。
线段树求矩形交的经典题。
首先离散化还是要去重，即使是浮点数，我的去重离散化模板还是稳得住的。
其次线段树节点中的cov要理解好。
最后跟标准线段树可以有些不同的，毕竟query永远是全部询问。
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<stack> #define ll long long #define maxn 1000 using namespace std; double t[maxn*4+5];//排序数组 double a[maxn*4+5];//原始数据 int b[maxn*4+5];//离散后的数据 double to[maxn*4+5];//离散后的数据到原数据的映射 struct tseg { int x1,x2,y; int flag;//+1表示下边，-1表示上边 bool operator<(const tseg& b) const { return y<b.y; } }; tseg seg[maxn*2+5]; struct ttree { int l,r; int cov;//cov是扫描线的重点 -1不确定 >=0完全覆盖次数 inline double len() { return to[r]-to[l]; } }; ttree tree[maxn*4*4+5]; void pushup(int x) { if(tree[x].l+1==tree[x].r) return; if(tree[x*2].cov==tree[x*2+1].cov) tree[x].cov=tree[x*2].cov; else tree[x].cov=-1; } void pushdown(int x) { if(tree[x].l+1==tree[x].r) return; if(tree[x].cov>=0) tree[x*2].cov=tree[x*2+1].cov=tree[x].cov; } void build(int x,int l,int r) { tree[x].l=l; tree[x].r=r; tree[x].cov=0; if(l+1<r) { int mid=(l+r+1)/2; build(x*2,l,mid); build(x*2+1,mid,r); } } void modify(int x,int l,int r,int op) { if(l<=tree[x].l&&r>=tree[x].r&&tree[x].cov>=0) { tree[x].cov+=op; } else { pushdown(x); int mid=(tree[x].l+tree[x].r+1)/2; if(l<mid) modify(x*2,l,r,op); if(r>mid) modify(x*2+1,l,r,op); pushup(x); } } //扫描线的query可以简略着写，因为一定是全部查询 double query(int x) { if(tree[x].cov>=2) return tree[x].len(); else if(tree[x].cov==0||tree[x].cov==1) return 0; else { pushdown(x); double ret=0; ret+=query(x*2); ret+=query(x*2+1); return ret; } } int main() { int tt; scanf("%d",&tt); while(tt--) { int n; scanf("%d",&n); for(int i=0;i<n*4;i++) { scanf("%lf",a+i); t[i]=a[i]; } sort(t,t+n*4); int m=unique(t,t+n*4)-t;//编号1..m for(int i=0;i<n*4;i++) { b[i+1]=lower_bound(t,t+m,a[i])-t+1; to[b[i+1]]=a[i]; } for(int i=1,j=1;i<=n*4;i+=4,j+=2) { seg[j]=(tseg){b[i],b[i+2],b[i+1],1}; seg[j+1]=(tseg){b[i],b[i+2],b[i+3],-1}; } sort(seg+1,seg+1+n*2); build(1,1,m); double ans=0; for(int i=1;i<=n*2;i++) { if(i>=2) { double len=query(1); ans+=len*(to[seg[i].y]-to[seg[i-1].y]); } modify(1,seg[i].x1,seg[i].x2,seg[i].flag); } printf("%.2f ",ans); } return 0; }