BOI02TRI - Triangles

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

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

Input

The first line of the input contains one positive integer n (n <= 2000), the number of triangles on a plane.

The next n lines of the file describe the triangles, one triangle per line. Each line contains three integers xi, yi and mi, separated by single spaces (1 <= i <= n, ‑107 <= xi <= 107, ‑107 <= yi <= 107, 0 < mi <= 1000).

Output

On the first line of the output one number with exactly one digit after decimal point must be written – the total area covered by triangles.

Example

Triangles
Input
5
-5 -3 6
-1 -2 3
 0 0 2
-2 2 1
-4 -1 2

Output
24.5

Added by:Faiyaz
Date:2014-07-11
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Baltic Informatics Olympiad 2002

hide comments
2017-10-16 11:22:09 [Rampage] Blue.Mary
The reason why a "semi-brute-force" solution can pass is the small range 0 < mi <= 1000.
2016-06-26 11:04:31 Piyush Kumar
Although the question is clear, the image is missing!

=(Francky)=> I can't fix this one ; email send to admin. Thanks for your catch.

Last edit: 2016-06-26 12:21:11
2014-10-27 21:10:07 Kshitij Gupta
Is the output supposed to have a ".0", if it is an integer?

Reply: Yes

Last edit: 2014-11-15 00:00:58
2014-08-03 10:30:12 fitcat
Finally AC with run time 0.00s again :)
Nice problem.

Last edit: 2014-08-03 17:22:49
2014-07-25 21:22:24 Faiyaz
Judge data is updated, and rejudge is in process. Sorry for it :)

Rejudge is done.

Last edit: 2014-07-25 21:41:33
2014-07-22 17:18:09 fitcat
@Mitch: Agreed. I was hesitated to submit my code (which got 0.00s) as I believe it could not complete in time in the worst (or not so worst) case.

Reply: Sorry, about the judge data. I have forgotten to enable all the judge data. I have changed them, and started rejudging. :)

Last edit: 2014-07-25 21:12:22
2014-07-13 01:46:45 Mitch Schwartz
Test data is too small/weak to allow reasonable speed comparison. It would be nice to have a properly prepared edition of the problem. I tested my code (which got 0.00s here) against an input file with { n=2000 ; x,y uniform random in [-10^4,10^4] ; m uniform random in [1,1000] }, and it was pretty slow: 3.61s (on Pyramid).

Reply: Sorry, about the judge data. I have forgotten to enable all the judge data. I have changed them, and started rejudging. :)

Last edit: 2014-07-25 21:12:08
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.