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 \leq n \leq 2 000$

$|x_i|, |y_i| \le 10^7$ $| x_{i} |, | y_{i} | \leq 10^{7}$

$1 \le m_i \le 1\,000$ $1 \leq m_{i} \leq 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 \leq i \leq n)$ .

Output Specification

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

Sample Input

Copy

Sample Output

Copy

24.5

Comments

0

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

Forest Area is a similar problem with higher constraints.