TopCoder problem "TriArea" used in SRM 268 (Division II Level Three)



Problem Statement

    We have a collection of possibly overlapping 45 degree isosceles right triangles. Each triangle is oriented with its hypotenuse at the bottom, parallel with the x axis. Each triangle is specified by giving the center point (xCenter,yCenter) of its hypotenuse and the height. For example, a triangle with center at (1,3) and with height 7 would have its three vertices at (-6,3), (8,3), and (1,10).

We need to know the area that is covered by the collection of triangles. Of course, we don't want to count overlapping areas multiple times. Create a class TriArea that contains a method area that is given int[]s xCenter, yCenter, and height and returns the area covered. The specification of the i-th triangle is given by the i-th element of xCenter, yCenter, and height.

 

Definition

    
Class:TriArea
Method:area
Parameters:int[], int[], int[]
Returns:double
Method signature:double area(int[] xCenter, int[] yCenter, int[] height)
(be sure your method is public)
    
 

Constraints

-xCenter will contain between 1 and 25 elements, inclusive.
-yCenter and height will have the same number of elements as xCenter.
-Each element of xCenter and yCenter will be between -100 and 100, inclusive.
-Each element of height will be between 1 and 100 inclusive.
 

Examples

0)
    
{1}


{3}
{7}
Returns: 49.0
This collection consists of just one triangle with a height of 7. This triangle has a base of 14 and an altitude of 7 so it has area 49.
1)
    
{1,1,1}
{3,3,3}
{7,7,8}
Returns: 64.0
The first two triangles in this collection are identical and the third triangle contains both of them, so the total area covered is just the area covered by the third one.
2)
    
{1,2}
{3,3}
{7,7}
Returns: 55.75
The area covered by these 2 triangles is the sum of their areas minus the area of their intersection. Their intersection is a 45 degree right triangle with height 6.5, so the result is 7*7 + 7*7 - 6.5*6.5 = 55.75.
3)
    
{3, 6, 10, 12}
{4, 11, -1, -7}
{2, 4, 6, 8}
Returns: 116.0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4699

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8001&pm=4699

Writer:

dgoodman

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force