PolygonSet | Topcoder Archive

Problem Statement

We call a set X good if:

|X| >= 3.
There exist a postive area polygon such that each side has a different length, and the set of lengths of sides is X.

You are given a set S, return the number of subsets that is good.

Definition

Class:: PolygonSet
Method:: count
Parameters:: int[]
Returns:: long
Method signature:: long count(int[] S)
(be sure your method is public)

Constraints

S will contain between 3 and 50 elements, inclusive.
Each number in S will be between 1 and 100, inclusive.
Numbers in S will be distinct.

Examples

```
{1,2,3,4}
```
```
Returns: 2
```
We have 2 good sets: {2,3,4} and {1,2,3,4}. Note that {1,2,3} is not good since the triangle will have an area equals to 0.
```
{90,91,92,93,94,95,96,97,98,99}
```
```
Returns: 968
```
Any subset with size at least 3 is good, so we have 2^10 - 1 - 10 - 10*9/2 = 968 good sets.
```
{2,5,8,7,4,3,9,1,6}
```
```
Returns: 402
```

{11,12,13,14,15,91,92,93,94,95}

Returns: 838

```
{1,2,3,4,5,6,7,8,9,100}
```
```
Returns: 402
```

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.