PointsInATriangle | Topcoder Archive

Problem Statement

Given a triangle on a plane, you must find the number of points with integer coordinates which are inside the given triangle. The points on the boundary must not be counted.

You will be given int[]s x and y, where (x[i], y[i]) represents the i-th vertex of the triangle.

Definition

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

Constraints

x and y will each contain exactly three elements.
Each element of x will be between -1000 and 1000, inclusive.
Each element of y will be between -1000 and 1000, inclusive.
The triangle specified by x and y will have non-zero area.

Examples

```
{0, 0, 4}
```
```
{0, 4, 0}
```
```
Returns: 3
```
The points in the triangle are (1, 1), (2, 1) and (1, 2).
```
{0, 0, 2}
```
```
{0, 2, 0}
```
```
Returns: 0
```
There are no integer points inside the triangle.
```
{-3, 2, 4}
```
```
{1, 6, -1}
```
```
Returns: 20
```
```
{-3, 4, 2}
```
```
{1,-1, 6}
```
```
Returns: 20
```

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.