F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 2731. -- [HNOI2012]三角形覆盖问题

2731: [HNOI2012]三角形覆盖问题

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 442  Solved: 259
[Submit][Status][Discuss]

Description

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

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

3 .
1 1 4
2 0 2
3 2 2

Sample Output

11.0

HINT

Source

day2

[Submit][Status][Discuss]

HOME Back