题目大意:给若干个矩形,统计重叠次数不为0的面积。

题目分析:维护扫描线的长度时,只需要只统计覆盖次数大于1的区间即可。这是个区间更新,不过不能使用懒标记,但是数据规模不大,不用懒惰标记仍可以AC。

代码如下:

# include<iostream>
# include<cstdio>
# include<map>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std;
# define mid (l+(r-l)/2) const int N=1000; void read(int &x)
{
x=0;
char c;
while((c=getchar())&&(c<'0'||c>'9'));
x=c-'0';
while(c=getchar()){
if(c<'0'||c>'9') break;
x=x*10+c-'0';
}
} //***************************************** struct Node
{
int c;
double len;
};
struct Segment
{
double x1,x2,y;
int d;
};
Segment seg[N*2+5];
map<double,int>mp;
vector<double>v;
Node tr[(N<<3)+5]; bool comp(const Segment &s1,const Segment &s2)
{
return s1.y<s2.y;
} void pushUp(int rt)
{
tr[rt].len=tr[rt<<1].len+tr[rt<<1|1].len;
} void build(int rt,int l,int r)
{
tr[rt].c=0;
tr[rt].len=0.0;
if(l==r) return ;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
} void update(int rt,int l,int r,int L,int R,int d)
{
if(l==r){
tr[rt].c+=d;
if(tr[rt].c>1) tr[rt].len=v[r]-v[l-1];
else tr[rt].len=0;
}else{
if(L<=mid) update(rt<<1,l,mid,L,R,d);
if(R>mid) update(rt<<1|1,mid+1,r,L,R,d);
pushUp(rt);
}
} int main()
{
//freopen("in.txt","r",stdin);
int T,n;
read(T);
while(T--)
{
read(n);
v.clear();
mp.clear();
double x1,x2,y1,y2;
for(int i=0;i<n;++i){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
seg[i<<1].x1=seg[i<<1|1].x1=x1;
seg[i<<1].x2=seg[i<<1|1].x2=x2;
seg[i<<1].y=y1,seg[i<<1|1].y=y2;
seg[i<<1].d=1,seg[i<<1|1].d=-1;
v.push_back(x1);
v.push_back(x2);
}
n<<=1;
sort(seg,seg+n,comp);
sort(v.begin(),v.end());
int m=unique(v.begin(),v.end())-v.begin();
for(int i=0;i<m;++i) mp[v[i]]=i+1; seg[n].y=seg[n-1].y;
build(1,1,m-1);
double ans=0.0;
for(int i=0;i<n;++i){
update(1,1,m-1,mp[seg[i].x1],mp[seg[i].x2]-1,seg[i].d);
ans+=tr[1].len*(seg[i+1].y-seg[i].y);
//cout<<tr[1].len<<endl;
}
printf("%.2lf\n",ans);
}
return 0;
}

  

最新文章

  1. .net App_Browser文件夹的作用
  2. 关于EF的一个简单Demo
  3. Building good docker images
  4. POJ 3672 Long Distance Racing (模拟)
  5. Posix IPC
  6. Nandflash 驱动移植
  7. java日历程序版本
  8. Callcenter 模块解析
  9. Python中加入中文注释
  10. [C#] VS2017中在某些目录下使用不了 .NET Core 2.0 问题的处理办法
  11. Python基础教程 - Tdcqma
  12. MPI-Hydra Process Managerment Framework
  13. [APM] OneAPM 云监控部署与试用体验
  14. 第 2 章 容器架构 - 007 - Docker 架构详解
  15. sqli-labs:11-16,post注入
  16. 机器学习理论基础学习14.1---线性动态系统-卡曼滤波 Kalman filter
  17. 用HTML5播放IPCamera视频
  18. Java中队列
  19. 《Spring2之站立会议2》
  20. CentOS 6.5安装配置Nginx

热门文章

  1. windows8.1安装
  2. 传Windows 9预览版今秋发布
  3. Java选择结构、循环结构
  4. 转:HashMap深度解析(一)
  5. poj1458
  6. 关于WinForm引用WPF窗体---在Winform窗体中使用WPF控件
  7. 聚簇(Cluster)和聚簇表(Cluster Table)
  8. Ubuntu 14.10 下安装Ganglia监控集群
  9. hdu 2041
  10. &lt;xliff:g&gt;标签