给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
注意:本题的输入数据较多,推荐使用scanf读入数据.
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
7.63 0.00
题解：
一开始想套上我的扫描线模板的，但是因为模板写法与一般写法有些不同，所以又重新打了一遍，抱着会tle的心态把区间更新改成了单点更新，然后判断覆盖的改成了2次或以上，结果样例答案居然差0.01，再抱着侥幸的心态加上了一个玄学的eps（很小的数），答案居然对了。。。。。然后抱着一定会wa的心态交上去。。居然ac了，acm真是奇妙啊hhhhhh，后来分析了下可能是数据比较小就能这样怼出来，用的时间有点多是1500ms，不过距离题目的5s还差很远，没看题解a出来很开心，一会再想想更快的方法。
然后如果不懂扫描线操作看我之前的博客有讲解：http://blog.csdn.net/qq_37497322/article/details/75126251
ps：
刚刚写出了这题超快的写法，附上链接：http://blog.csdn.net/qq_37497322/article/details/77297203
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<deque>
using namespace std;
#define lson k*2
#define rson k*2+1
#define M (t[k].l+t[k].r)/2
#define INF 1008611111
#define ll long long
#define eps 1e-15//玄学
struct node
{int l,r;double len;int v;//覆盖次数
}t[2005*4];
double xx[2005];
void Build(int l,int r,int k)
{t[k].l=l;t[k].r=r;t[k].len=0.0;t[k].v=0;if(l==r)return;int mid=M;Build(l,mid,lson);Build(mid+1,r,rson);
}
void pushup(int k)//扫描线区间合并
{if(t[k].v>1){t[k].len=xx[t[k].r+1]-xx[t[k].l];}else{t[k].len=t[lson].len+t[rson].len;}
}
void update(int l,int r,int k,int d)//把扫描线模板的区间更新改成了区间下的单点更新
{if(l<=t[k].l&&t[k].r<=r&&t[k].r==t[k].l){t[k].v+=d;pushup(k);return;}int mid=M;if(l<=mid)update(l,r,lson,d);if(r>mid)update(l,r,rson,d);pushup(k);
}
struct edge
{double l,r;double h;int d;
}a[2005];
int cmp(edge x,edge y)//按高度从小到大排序
{if(x.h!=y.h)return x.h<y.h;return x.d<y.d;
}
int main()
{int i,j,k,n,tot,l,r,test,ans;double x1,x2,y1,y2;scanf("%d",&test);while(test--){scanf("%d",&n);tot=0;for(i=0;i<n;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);a[tot].l=x1;a[tot].r=x2;a[tot].h=y1;a[tot].d=1;a[tot+1].l=x1;a[tot+1].r=x2;a[tot+1].h=y2;a[tot+1].d=-1;xx[tot]=x1;xx[tot+1]=x2;tot+=2;}sort(xx,xx+tot);sort(a,a+tot,cmp);ans=unique(xx,xx+tot)-xx;//去重Build(0,ans-1,1);double s=0;for(i=0;i<tot;i++){int l=lower_bound(xx,xx+ans,a[i].l)-xx;int r=lower_bound(xx,xx+ans,a[i].r)-xx-1;update(l,r,1,a[i].d);s+=(t[1].len*(a[i+1].h-a[i].h));}printf("%.2lf\n",s+eps);//玄学eps}return 0;
}