Connection Status:
Competition Arena > UniqueTriangles

UniqueTriangles

TCCC '04 Round 2 · 2004-02-23 · by Yarin

TCCC '04 Round 2 · 2004-02-23 · by Yarin · Brute Force, Geometry
Class Name: UniqueTriangles
Return Type: int
Method Name: howMany
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Given n points in the cartesian coordinate system, how many uniquely shaped triangles can you construct by letting 3 of these points be the corners of a triangle? Two triangles are unique if they are not similar - that is, if it's not possible to transform one triangle into the other by any means of rotating, flipping and/or scaling. See example 0 for further clarifications.

Create a class UniqueTriangles which contains the method howMany that takes as input a int[] x and int[] y, the coordinates of the n points, and returns an int, the number of unique triangles. Element i in x and y corresponds to one point.

Notes

  • All angles in a triangle must be strictly greater than zero.
  • Hint: Two triangles are similar if a1/a2 = b1/b2 = c1/c2 where ai, bi and ci are the sides in one triangle (in some order).

Constraints

  • x will contain between 3 and 50 elements, inclusive.
  • y will contain the same number of elements as x.
  • Each element in x will be between -10000 and 10000, inclusive.
  • Each element in y will be between -10000 and 10000, inclusive.
  • No point will occur more than once.
Examples
0)
{0,1,1,0,2}
{0,1,0,1,0}
Returns: 3

If we first consider all triangles that can be created using only the points (0,0), (1,1), (1,0) and (0,1), we see that all such triangles will have two sides with length 1 and one side with length sqrt(2). Now, if we also take into consideration the point (2,0), we also get the triangles: a) (2,0)-(0,0)-(0,1) b) (2,0)-(0,0)-(1,1) c) (2,0)-(0,1)-(1,1) d) (2,0)-(1,0)-(0,1) c) and d) are similar (flip), and b) is similar with the triangles between the first four points (larger and rotated). There are no more possible triangles, so the method should return 3.

1)
{0,8,-3,1000,-9500,-1}
{7,15,4,1007,-9493,6}
Returns: 0

All points lie on a straight line, thus there are no triangles at all. The method should return 0.

2)
{-4,2,5,-5,-4,-4,3,1,1,1,2,0,1,1,5}
{5,2,-4,2,1,3,1,-1,2,0,1,4,-3,1,0}
Returns: 256
3)
{-24,-22,33,78,-77,-66,76,-54,32,40,
 -66,-22,-88,-50,-11,93,16,34,-79,-60,
 -42,-30,-73,65,92,94,67,-74,69,83,
 -51,91,78,-30,91,85,-78,-5,36,-91}
{91,14,27,-98,35,-14,-89,-12,-78,57,
 6,-52,-65,-61,-60,46,-84,34,31,11,
 41,97,-54,47,-12,-69,19,96,43,-45,
 -38,-71,53,6,-2,-43,-43,15,17,-77}
Returns: 9872
4)
{0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5,0,1,2,3,4,5}
{0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5}
Returns: 119

Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class UniqueTriangles with a public method int howMany(vector<int> x, vector<int> y) · 44 test cases · 2 s / 256 MB per case

Submitting as anonymous