Description

二维平面中,给定   N个等腰直角三角形(每个三角形的两条直角边分别
 
 
平行于坐标轴,斜边从左上到右下)。我们用三个非负整数( xyd)来描
 
述这样一个三角形,三角形三个顶点的坐标
 
分别为(xy), (x + dy)和(xy +     d)。要求计算这   N个三角形所覆盖的总面
 
积。例如,下图有 3 个三角形,覆盖的总面积为 11.0。
 

Input

输入文件第一行为一个正整数N,表示三角形的个数。接下来的 N

行每行有用空格隔开的三个非负整数,  xy   , d,描述一个三角

形的顶点坐标,分别为

(    xy), (x + dy), (  xy+d),

其中 xyd 满足0≤   xyd≤1000000。

对于50%的数据,1≤         N≤500;

100%的数据,1≤N≤10000。

Output

仅包含一行,为一个实数    S    ,表示所有三角形所覆盖的总面积,输出恰

好保留一位小数。输入数据保证     S≤2^31 。

Sample Input

3 .
1 1 4
2 0 2
3 2 2

Sample Output

11.0

题解:

将所有三角形按照底边的y坐标升序排序,然后用一根扫描线,从最下面的三角形的底边开始向上扫,并时刻维护sum[]数组和len,sum[i]=第i格上覆盖的三角形个数(注意是第i格而不是第i个点!第i个点和第i+1个点之间的那一格就是第i格),len=扫描线上被覆盖的部分的总长度(以下简称有效长度),显然移动完一次扫描线后,答案中增加的面积=$$\frac{上次扫描线的有效长度+本次扫描线的有效长度}{2}$$

那么实际上整个题要做的就是从最下面不断地向上移动扫描线,用一个栈维护覆盖在扫描线上面的三角形,每移动一次扫描线,先维护一次有效长度和sum[]数组,但是这次维护只是在原有的三角形基础上减少,并不增加三角形(也就是说这次维护是不添加新相交的三角形的,有效长度只会减少,不会增加)!在答案中添加面积后,再对扫描线上的有效长度和sum[]数组这两个信息进行第二次维护,这次会加入移动扫描线后新相交的三角形。如此反复便可得到答案。

但是这样做还是会TLE掉最后两个点,因此我们需要再想办法优化,可以发现,某些小三角形是被大三角形所包裹起来的(如下图中红叉的那个紫色三角形,虚线是扫描线,箭头是扫描线的移动方向),显然这样的小三角形都可以忽略不计,因此可以大大减少数据规模。

那么我们可以标记每个三角形是否已经被删除了,在每次扫描线移动后,在加入新的三角形的时候,看这个三角形是否包裹了原来的三角形,以及这个三角形是否被原来的三角形所包裹。若这个三角形包裹了原来的三角形,就把原来的那个三角形删掉,如此下去,如果这个三角形并没有被原来扫描线上的三角形包裹,那么就把它加入扫描线上,并更新对应于扫描线上的区间的格子的信息。 
要做到轻松地删除三角形,并通过这样的优化减少数据规模的话,就需要用一个双向链表来维护当前所有还没被删掉的三角形,当然也可以用splay来维护的啦,速度会快很多。

 //Never forget why you start
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
struct triangle {
int x,y,d,l,r;//横坐标,纵坐标,直角边长,左端点横坐标,右端点横坐标
friend bool operator > (const triangle a,const triangle b) {
return a.l<=b.l&&b.r<=a.r;
}//定义一个三角形a左右两端点如果完全包含另外一个三角形b,则a>b
} a[];
int Next[],pre[],vis[],head,mmax,mmin,len,lastlen,sum[],top,stack[];
//Next[]表示双向链表的下一个数
//pre[]表示双向链表的上一个数
//vis[]表示是否在双向链表中
//head表示双向链表的第一个点
double ans;
void delet(int x) {
vis[x]=;
if(head==x)head=Next[x];
pre[Next[x]]=pre[x];
Next[pre[x]]=Next[x];
}//从双向链表中删除一个数
bool cmp(triangle a,triangle b) {
if(a.y==b.y)return a.l<=b.l&&b.r<=a.r;
else return a.y<b.y;
}//比较函数,先按y从小到大排序,再使前面的三角形完全包含后面的三角形
int main() {
int i,j,k,l;
scanf("%d",&n);
for(i=; i<=n; i++) {
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d);
a[i].r=a[i].x+a[i].d;
a[i].l=a[i].x;
vis[i]=;
Next[i]=i+;
pre[i]=i-;
mmin=min(mmin,a[i].y);
mmax=max(mmax,a[i].y+a[i].d);
}//输入,初始化双向链表
sort(a+,a+n+,cmp);//排序
head=;
for(i=head; i<=n&&a[i].y==mmin; i=Next[i]) {
for(j=a[i].l; j<a[i].r; j++) {
if(!sum[j])len++;
sum[j]++;
}
}//统计最开始被三角形覆盖的长度
for(i=mmin+; i<=mmax; i++) {
lastlen=len;//lastlen表示层被覆盖的长度,len表示这一层备覆盖的长度
top=;//初始化栈
for(j=head; j<=n&&a[j].y<i; j=Next[j]) {//遍历上一层已经计算过的三角形
a[j].r--;//因为向上挪了一层,就相当于宽度减小了1
if(a[j].r<a[j].l)delet(j);//如果这个三角形完全消失,则从双向链表中删去
else {
if(sum[a[j].r]==)len--;//判断r--后是否对len的大小造成影响
sum[a[j].r]--;
stack[++top]=j;//将这个三角形压入栈中(这个三角形覆盖了一部分长度)
}
}
ans+=(double)(lastlen+len)/2.0;//计算答案
for(j=head; j<=n&&a[j].y<=i; j=Next[j]) {
if(a[j].y==i) {//遍历所有覆盖在当前层的三角形
for(k=; k<=top; k++) {//遍历所有在栈中的三角形,
if(vis[stack[k]]==)continue;
if(a[stack[k]]>a[j]) {//判断当前三角形是非已被栈中某个三角形覆盖
delet(j);//如果已经覆盖,就在双向链表中将这个三角形删除
break;
}
if(a[j]>a[stack[k]]) {
delet(stack[k]);
for(l=a[stack[k]].l; l<a[stack[k]].r; l++) {
if(sum[l]==)len--;
sum[l]--;
}//如果栈中三角形被当前三角形覆盖,就删除栈中三角形
}
}
if(k==top+) {//如果所有栈中三角形都无法将当前三角形覆盖,就加入当前三角形
for(l=a[j].l; l<a[j].r; l++) {
if(!sum[l])len++;
sum[l]++;
}
}
}
}
}
printf("%.1lf\n",ans);
return ;
}

最新文章

  1. Git 简易手册
  2. C#中关于异步的三种写法
  3. store.js - 轻松实现本地存储(LocalStorage)
  4. Listview的闪烁问题
  5. Spring项目跟Axis2结合
  6. JS中 判断null
  7. 【KMP原理】【整理回顾】
  8. SqlServer中decimal(numeric )、float 和 real 数据类型的区别[转]
  9. poj 1940 Wine Trading in Gergovia_贪心
  10. UVA 10163 Storage Keepers(dp + 背包)
  11. Python 线程,进程
  12. 基于LNMP的Zabbbix之PHP源码安装
  13. ios NSString拼接方法总结
  14. 提交代码,SVN被锁定,提示:svn is already locked解决方案
  15. [UE4]插值interp
  16. hadoop3.x的安装
  17. maven library has broken path和pom jar包导入失败
  18. hadoop_批量命令脚本&amp;同步文件脚本
  19. 使用bat批处理文件备份postgresql数据库
  20. Swift的Guard语句

热门文章

  1. Gym-101673: A Abstract Art (模板,求多个多边形的面积并)
  2. 「P4994」「洛谷11月月赛」 终于结束的起点(枚举
  3. 洛谷P1525关押罪犯——并查集
  4. Will&amp;nbsp;you&amp;nbsp;still&amp;nbsp;need&amp;nbsp;me?
  5. error: field has incomplete type
  6. BDBR vs BDPSNR 计算方法 (转载)
  7. JavaScript操作服务器控件之Gridview控件
  8. C#—反射(反射类型、方法、构造函数、属性、实现可配置可扩展、数据库访问类反射封装)
  9. Spring Security 表达式(Expressions) - hasRole示例
  10. 跟我学: 使用 fireasy 搭建 asp.net core 项目系列之一 —— 开篇