Connection Status:
Competition Arena > TriArea

TriArea

SRM 268 · 2005-10-18 · by dgoodman

SRM 268 · 2005-10-18 · by dgoodman · Brute Force
Class Name: TriArea
Return Type: double
Method Name: area
Arg Types: (vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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)
{-100, -100, 100, 100}
{100, -100, -100, 100}
{100, 100, 100, 100}
Returns: 40000.0
4)
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18}
{-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-5}
{9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9}
Returns: 229.75

Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TriArea with a public method double area(vector<int> xCenter, vector<int> yCenter, vector<int> height) · 51 test cases · 2 s / 256 MB per case

Submitting as anonymous