三角形覆盖问题
提交数: 6, 通过率: 16.67%, 平均分: 16.67
题目描述:
二维平面中,给定 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≤2^31 。
样例输入:
3 1 1 4 2 0 2 3 2 2
样例输出:
11.0时间限制: 2000ms
空间限制: 256MB
来源: 湖南省选2012day2t1