TriangleCounting
Rookie SRM 11 · 2022-03-24 · by erinn
Problem Statement
You are given a set of points in
Return the number of ways you can select three of the given points to form a triangle.
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.
{ 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.
Submissions are judged against all 24 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TriangleCounting with a public method int count(vector<int> x, vector<int> y) · 24 test cases · 2 s / 256 MB per case