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.
|
| |
Definition |
| | | Class: | UniqueTriangles | | Method: | howMany | | Parameters: | int[], int[] | | Returns: | int | | Method signature: | int howMany(int[] x, int[] y) | | (be sure your method is public) |
|
| |
|
| |
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) | |
| | | 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 | |
|