NonSimilarTriangles | Topcoder Archive

Problem Statement

You have a collection of straight sticks. The lengths of these sticks are given in the int[] L. You are going to use three of these sticks to form a triangle.

Two triangles are called similar if one of them can be translated, rotated, mirrored, and/or uniformly scaled (in any order) to produce the other one. For example, any triangle with sides 30, 40, and 50 is similar to any triangle with sides 500, 300, and 400, and also to any triangle with sides 33, 55, and 44.

Consider all possible triangles that can be formed using three of your sticks. Suppose we divide these triangles into groups, each group being a collection of triangles that are similar to each other. How many groups will there be? In other words, how many different (i.e., non-similar) triangles can be constructed using three of your sticks? Compute and return this number.

Definition

Class:: NonSimilarTriangles
Method:: count
Parameters:: int[]
Returns:: int
Method signature:: int count(int[] L)
(be sure your method is public)

Notes

A valid triangle must have a positive area. (See Example 5.)

Constraints

L will have between 3 and 150 elements, inclusive.
Each element of L will be between 1 and 10^6, inclusive.

Examples

```
{3,4,5}
```
```
Returns: 1
```
We can build exactly one triangle.
```
{1,1,1,1,1,1}
```
```
Returns: 1
```
Regardless of which three sticks we choose, we will get the same triangle: an equilateral triangle with side length 1.
```
{2,2,2,3,3,3}
```
```
Returns: 3
```
There are three different triangles we can build: an equilateral triangle (with side 2 or side 3, those are similar to each other), a triangle with sides 2,2,3, or a triangle with sides 2,3,3.
```
{1,2,4,8,16,24}
```
```
Returns: 0
```
We cannot build any triangles at all: regardless of which three sticks you pick, you won't be able to build a valid triangle.

{10,3,10,4,10,5,10,6,10,7,10,8,10,9}

Returns: 50

```
{5, 5, 10}
```
```
Returns: 0
```
These three sticks do not form a valid triangle. A valid triangle must have a positive area.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.