题意:给你n个矩形,然后矩形有可能重叠,要你求周长

思路:首先碰到这种矩形在数轴上那么第一反应应该想到的是扫描线,

做周长我们有两种方法

第一种,我们可以分开两部分求,第一遍求x轴上的贡献,第二遍求y轴上的贡献

首先第一条边我们可以直接加出贡献,第二条边我们和第一条有覆盖部分,那么我们要怎么加呢,我们会发现要加的也就是  ( 加入这条边后的线段树上最大长度-没加之前的最大长度)

然后我们再加进来,会看到加入出边的时候因为是-1了,所以加入后的长度会比没加之前的值小,但是贡献依然是他们的差值,那么我们就只要求绝对值即可

y轴上是一样的道理

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define N 10005
#define ll long long
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct Seg
{
int l,r,h;
int f;
Seg() {}
Seg(int a,int b,int c,int d):l(a),r(b),h(c),f(d) {}
bool operator < (const Seg &cmp) const
{
return h<cmp.h;
}
} e[N],e2[N];
struct node
{
int cnt;
int len;
} t[N<<];
int X[N];
int Y[N];
void pushdown(int l,int r,int rt,int X[])
{
if(t[rt].cnt)//当前的边被标记,就把当前的长度加上
t[rt].len=X[r+]-X[l];
else if(l==r)//当为一个点的时候长度为0
t[rt].len=;
else//其他情况把左右两个区间的值加上
t[rt].len=t[rt<<].len+t[rt<<|].len;
}
void update(int L,int R,int l,int r,int rt,int val,int X[])
{
if(L<=l&&r<=R)
{
t[rt].cnt+=val;//加上标记的值
pushdown(l,r,rt,X);//像下更新节点
return;
}
int m=(l+r)>>;
if(L<=m) update(L,R,lson,val,X);
if(R>m) update(L,R,rson,val,X);
pushdown(l,r,rt,X);
}
int main()
{
int n;
int a,b,c,d;
while(scanf("%d",&n)!=EOF)
{
mem(t,);
int num=;
for(int i=; i<n; i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
X[num]=a;Y[num]=b;
e[num]=Seg(a,c,b,);//矩形下面用1来标记吗
e2[num++]=Seg(b,d,a,);
X[num]=c;Y[num]=d;
e[num]=Seg(a,c,d,-);//上面用-1来标记
e2[num++]=Seg(b,d,c,-);
}
sort(Y,Y+num);
sort(X,X+num);//用于离散化
sort(e,e+num);//把矩形的边的纵坐标从小到大排序
sort(e2,e2+num);
int m=unique(X,X+num)-X;
int m2=unique(Y,Y+num)-Y;
int ans=;
int last=;
for(int i=; i<num; i++)
{
int l=lower_bound(X,X+m,e[i].l)-X;//找出离散化以后的值
int r=lower_bound(X,X+m,e[i].r)-X-;
update(l,r,,m,,e[i].f,X);
ans+=abs(last-t[].len);
last=t[].len;
}
last=;
memset(t,,sizeof(t));
for(int i=; i<num; i++)
{
int l=lower_bound(Y,Y+m2,e2[i].l)-Y;//找出离散化以后的值
int r=lower_bound(Y,Y+m2,e2[i].r)-Y-;
update(l,r,,m2,,e2[i].f,Y);
ans+=abs(last-t[].len);
last=t[].len;
}
printf("%d\n",ans);
}
return ;
}

第二种我暂时不会,先空着,只要求一遍扫描线

最新文章

  1. lua的私有性(privacy)
  2. sql索引组织
  3. qt之esc键
  4. 高级I/O之非阻塞I/O
  5. 深度模拟java动态代理实现机制系类之一
  6. pydev-python 链接mysql数据库(mac系统)
  7. 【SCOI2008】着色方案
  8. Django查询笔记1
  9. ios开发-指纹识别
  10. 浅拷贝 &amp;&amp;&amp;深拷贝 实现
  11. Vue 组件异步加载(懒加载)
  12. bootstrap实现列的拖动
  13. Python:从入门到实践--第十章--文件和异常--练习
  14. SQL作业
  15. (并查集)Travel -- hdu -- 5441(2015 ACM/ICPC Asia Regional Changchun Online )
  16. Anaconda3+python3环境下如何创建python2环境(win+Linux下适用,同一个anaconda下py2/3共存)
  17. JQuery中事件one、bind、unbind、live、delegate、on、off、trigger、triggerHandler的各种使用区别
  18. 《Linux Device Drivers》第十五章 内存映射和DMA——note
  19. LevelDB 读取记录
  20. Kivy: Building GUI and Mobile apps with Python

热门文章

  1. mysql8.0.15出错
  2. 【CF1100F】Ivan and Burgers(线性基,分治)
  3. 2018-2019-2 20175105王鑫浩《Java程序设计》实验四 《Android开发基础》实验报告
  4. JS获取浏览器地址栏的多参数值的任意值
  5. C#-Newtonsoft.Json遍历并修改JSON
  6. 测开之路二十六:Flask基础之最小web程序
  7. Note1
  8. 记C函数指针的“小坑”
  9. python 装饰器 对类和函数的装饰
  10. OSG+Visual Studio2015项目变量设置;