参考  https://www.cnblogs.com/null00/archive/2012/04/22/2464876.html

#include <stdio.h>
#include <algorithm>
#define LEN 10000
using namespace std; struct Node
{
int left;
int right;
int count;//被覆盖次数
//所包含的区间数量,如三条[1,2],[2,3],[4,5]线段被覆盖,则line=2,因为 [1,2],[2,3]是连续的。
int line;//所包含的区间数量
int lbd;//左端点是否被覆盖 用来辅助对line的计算
int rbd;//右端点是否被覆盖
int m;//测度 ,即覆盖的区间长度,如[2,8]就为6
}node[LEN*];;
struct ScanLine
{
int x;
int y1;
int y2;
int flag;
}scan[LEN];;
int y[LEN];
void build(int l, int r, int i)
{
node[i].left = l;
node[i].right = r;
node[i].count = ;
node[i].m = ;
node[i].line = ;
if (r - l > )
{
int middle = (l + r)/;
build(l, middle, *i + );
build(middle, r, *i + );
}
}
//更新测度m
void update_m(int i)
{
if (node[i].count > )
node[i].m = y[node[i].right] - y[node[i].left];
else if (node[i].right - node[i].left == )
node[i].m = ;
else
{
node[i].m = node[*i + ].m + node[*i + ].m;
}
}
//更新line
void update_line(int i)
{
if (node[i].count > )
{
node[i].lbd = ;
node[i].rbd = ;
node[i].line = ;
}
else if (node[i].right - node[i].left == )
{
node[i].lbd = ;
node[i].rbd = ;
node[i].line = ;
}
else
{
node[i].lbd = node[*i + ].lbd;
node[i].rbd = node[*i + ].rbd;
node[i].line = node[*i + ].line + node[*i + ].line - node[*i + ].rbd*node[*i + ].lbd;
}
}
void insert(int l, int r, int i)
{
//在这里要取离散化之前的原值进行比较
if (y[node[i].left] >= l && y[node[i].right] <= r)
(node[i].count)++;
else if (node[i].right - node[i].left == )
return;
else
{
int middle = (node[i].left + node[i].right)/;
if (r <= y[middle])
insert(l, r, *i + );
else if (l >= y[middle])
insert(l, r, *i + );
else
{
insert(l, y[middle], *i + );
insert(y[middle], r, *i + );
}
}
update_m(i);
update_line(i);
} void remove(int l, int r, int i)
{
////在这里要取离散化之前的原值进行比较
if (y[node[i].left] >= l && y[node[i].right] <= r)
(node[i].count)--;
else if (node[i].right - node[i].left == )
return;
else
{
int middle = (node[i].left + node[i].right)/;
if (r <= y[middle])
remove(l, r, *i + );
else if (l >= y[middle])
remove(l, r, *i + );
else
{
remove(l, y[middle], *i + );
remove(y[middle], r, *i + );
}
}
update_m(i);
update_line(i);
} bool cmp(ScanLine line1,ScanLine line2)
{
if (line1.x == line2.x)
return line1.flag > line2.flag;
return (line1.x < line2.x);
} int main()
{
int n;
scanf("%d", &n);
int x1, y1, x2, y2;
int i = ;
while (n--)
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
scan[i].x = x1;
scan[i].y1 = y1;
scan[i].y2 = y2;
scan[i].flag = ;
y[i++] = y1;
scan[i].x = x2;
scan[i].y1 = y1;
scan[i].y2 = y2;
scan[i].flag = ;
y[i++] = y2;
}
sort(y, y + i);
sort(scan, scan + i, cmp);
//y数组中不重复的个数
int unique_count = unique(y, y + i) - y;
//离散化,建立线段树
build(, unique_count - , );
int perimeter = ;
int now_m = ;
int now_line = ;
for (int j = ; j < i; j++)
{
if (scan[j].flag)
insert(scan[j].y1, scan[j].y2, );
else
remove(scan[j].y1, scan[j].y2, );
if (j >= )
perimeter += *now_line*(scan[j].x - scan[j-].x);
//要减去,因为一个边只能算一次,要减去上一次已经算过的边
perimeter += abs(node[].m - now_m);
now_m = node[].m;
now_line = node[].line;
}
printf("%d\n", perimeter);
return ;
}

最新文章

  1. mysql乱码解决
  2. java中的URLConnection和HttpURLConnection
  3. Microsoft ACE OLEDB 12.0概念及用法
  4. SRS文档 软件需求说明书
  5. 怎么通过 Microsof Office Project 2010 来写功能开发计划
  6. Python的运行
  7. javaSE基础之记事本编程
  8. show index 之Cardinality (mysql)
  9. Linux之cuda安装
  10. 独立两套DJANGO+CELERY配置(生产+测试)时要注意的一些细节
  11. Android 定时任务高度【schedule】与【scheduleAtFixedRate】差别
  12. 兼容主流浏览器的js原生函数封装
  13. zabbix安装及简单使用备注
  14. ___树形菜单Ztree.js显示.
  15. [转]调试利器-SSH隧道
  16. 最全的MonkeyRunner自动化测试从入门到精通(6)
  17. iOS设计模式 - 访问者
  18. 【bzoj3122】 Sdoi2013—随机数生成器
  19. HDU 1160 FatMouse&#39;s Speed (最长上升子序列)
  20. 关于volatile 最完整的一篇文章

热门文章

  1. python学习方法
  2. 洛谷P1649 【[USACO07OCT]障碍路线Obstacle Course】
  3. Jenkins report 打开样式失败解决方案
  4. Codeforces_711_A
  5. (三)maven创建部署javaweb
  6. 异步并发利器:实际项目中使用CompletionService提升系统性能的一次实践
  7. 2.【Spring Cloud Alibaba】实现负载均衡-Ribbon
  8. [Redis-CentOS7]Redis字符串操作(二)
  9. js类的constructor中不支持异步函数吗?
  10. android系统webview使用input实现选择文件并预览