TriangleCounting | Topcoder Archive

Problem Statement

You are given a set of points in int[]s x and y, where each (x[i], y[i]) are the coordinates of one of the points. A set of three points form a triangle if and only if they are not colinear.

Return the number of ways you can select three of the given points to form a triangle.

Definition

Class:: TriangleCounting
Method:: count
Parameters:: int[], int[]
Returns:: int
Method signature:: int count(int[] x, int[] y)
(be sure your method is public)

Constraints

x will contain between 1 and 50 elements, inclusive.
x and y will contain the same number of elements.
Each element of x and y will be between 0 and 1000, inclusive.

Examples

```
{ 0, 2, 4 }
```
```
{ 0, 5, 3 }
```
```
Returns: 1
```
There's exactly three points, and they form a triangle.
```
{ 0, 2, 4, 6 }
```
```
{ 0, 5, 3, 15 }
```
```
Returns: 3
```
There's four ways to select three points here, but note that the points (0,0), (2,5), (6,15) are colinear, and thus don't form a triangle. So there are only three good sets to select.
```
{ 0, 2, 6 }
```
```
{ 0, 5, 15 }
```
```
Returns: 0
```
Here, we have only a single set to select, and those three points are colinear, so there are no triangles to speak of.

{ 0, 2, 4, 6, 8 }

{ 0, 5, 3, 15, 6 }

Returns: 8

```
{ 0, 1, 2, 3, 4, 5, 6 }
```
```
{ 1, 2, 3, 4, 5, 6, 7 }
```
```
Returns: 0
```
Lots of points, but they're all on a single line, so none can form a triangle.
```
{ 0, 0, 1 }
```
```
{ 0, 0, 1 }
```
```
Returns: 0
```
Two of the points are at the same location, so, of course, they don't form a triangle.

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.