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
Input 5 -5 -3 6 -1 -2 3 0 0 2 -2 2 1 -4 -1 2 Output 24.5
hide comments
[Rampage] Blue.Mary:
2017-10-16 11:22:09
The reason why a "semi-brute-force" solution can pass is the small range 0 < mi <= 1000. |
|
Piyush Kumar:
2016-06-26 11:04:31
Although the question is clear, the image is missing!
|
|
Kshitij Gupta:
2014-10-27 21:10:07
Is the output supposed to have a ".0", if it is an integer?
|
|
fitcat:
2014-08-03 10:30:12
Finally AC with run time 0.00s again :)
|
|
Faiyaz:
2014-07-25 21:22:24
Judge data is updated, and rejudge is in process. Sorry for it :)
|
|
fitcat:
2014-07-22 17:18:09
@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.
|
|
Mitch Schwartz:
2014-07-13 01:46:45
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).
|
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 |