问题 6180. -- NOI2012湖北省选 二试 第1题 三角形覆盖问题

6180: NOI2012湖北省选 二试 第1题 三角形覆盖问题

时间限制: 2 Sec  内存限制: 512 MB
献花: 0  解决: 0
[献花][花圈]

题目描述

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

三角形,覆盖的总面积为11.0。


输入

第一行为一个正整数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。

输出

仅包含一行,为一个实数S,表示所有三角形所覆盖的总面积,输出恰好保留一位小数。输入数据保证S≤231

样例输入

3
1 1 4
2 0 2
3 2 2

样例输出

11.0

提示

来源

[献花][花圈]