Description
Input
输入文件第一行为一个正整数N，表示三角形的个数。接下来的 N
行每行有用空格隔开的三个非负整数， x, y , d，描述一个三角
形的顶点坐标，分别为
( x, y), (x + d, y), ( x, y+d)，
其中 x, y, d 满足0≤ x, y, d≤1000000。
对于50%的数据，1≤ N≤500；
100%的数据，1≤N≤10000。
Output
仅包含一行，为一个实数 S ，表示所有三角形所覆盖的总面积，输出恰
好保留一位小数。输入数据保证 S≤2^31 。
Sample Input
1 1 4
2 0 2
3 2 2
Sample Output
题解：
将所有三角形按照底边的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 ;
}