Baltic OI '02 P3 - Triangles - Olympiads Online Judge

Baltic OI '02 P3 - Triangles

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem types

Baltic Olympiad in Informatics: 2002 Day 1, Problem 3

There are given $n$ ~n~ isosceles right triangles on a plane. Each triangle can be described by three integers $x, y, m$ ~x, y, m~. Vertices of such a triangle are points which have coordinates $(x, y)$ ~(x, y)~, $(x+m, y)$ ~(x+m, y)~ and $(x, y+m)$ ~(x, y+m)~.

Write a program which calculates the total area covered by triangles.

Constraints

$1 \le n \le 2\,000$ ~1 \le n \le 2\,000~

$|x_i|, |y_i| \le 10^7$ ~|x_i|, |y_i| \le 10^7~

$1 \le m_i \le 1\,000$ ~1 \le m_i \le 1\,000~

Input Specification

The first line of input contains one positive integer $n$ ~n~, the number of triangles on a plane.

The next $n$ ~n~ lines describe the triangles, one triangle per line. Each line contains three space-separated integers $x_i$ ~x_i~, $y_i$ ~y_i~ and $m_i$ ~m_i~ $(1 \le i \le n)$ ~(1 \le i \le n)~.

Output Specification

Output one number with exactly one digit after the decimal point - the total area covered by triangles.

Sample Input

Sample Output

24.5

Comments

0

d commented on Nov. 25, 2022, 10:02 a.m.

Forest Area is a similar problem with higher constraints.