Statistics

Problem Statement for "UniqueTriangles"

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

  1. {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.

  2. {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.

  3. {-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

  4. {-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

  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,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

  6. {-26,20,0,15,13,18,17,18,-25,-2,-3,12,-6,9,0,-5,12,-27,-25,10}

    {25,-5,-17,18,-2,7,5,-25,-25,-4,27,-12,-3,-8,-23,-22,-25,-23,17,17}

    Returns: 1128

  7. {25,-5,21,-22,36,-45,-45,-5,-17,-1,-35,41,-50,-50,-44,-25,-3,-26,39,23,12,44,19,-5,-47}

    {17,-38,-42,-2,-36,4,-35,-3,39,28,17,0,-19,-48,-1,-36,-47,25,-43,40,-5,23,-9,48,44}

    Returns: 2291

  8. {0,0,0,0, 0, 0, 0, 0,1,2,3,4,-1,-2,-3,-4}

    {1,2,3,4,-1,-2,-3,-4,0,0,0,0, 0, 0, 0, 0}

    Returns: 48

  9. {0,1,4,3}

    {0,3,4,1}

    Returns: 2

  10. {-7566,-9000,-4728,-4820,-2064,-3424,-8340,7285,-4894,3106,-4415,-1993,-4406,-4047,-1842,-640,3675,9152,3534,-6434,5819,-844,-7993,9196,2677,96,3660,-8487,-4901,4027}

    {5310,1194,-9898,-1891,3236,2048,-7137,2198,7323,-2084,-3544,-6410,-96,1126,7,-3519,3009,1373,-4600,5218,986,5019,-9881,-3580,1774,1303,217,-565,1649,982}

    Returns: 4060

  11. {-1,6,5,0,-9,-3,1,9,10,2,-2,-2,-6,-2,-2,6,4,-1,-9,-5,8,-9,0,-7,-4,3,5,5,-1,-1}

    {-3,-1,6,0,-7,7,0,4,-4,6,5,-6,-2,9,-9,7,3,10,-10,5,9,2,-7,2,3,1,10,-6,-5,-6}

    Returns: 2637

  12. {3,5,-1,-3,-3,-1,4,3,1,-1,2,2,-4,-1,4,0,5,2,-4,1,0,-2,4,1,1,3,3,-4,3,-2}

    {0,-4,2,-2,2,-3,-3,-1,0,1,1,4,-4,5,-1,-2,5,5,-5,-2,4,2,5,-1,-4,-2,4,5,2,-2}

    Returns: 871

  13. {-364,697,-770,-114,662,487,700,-429,443,405,-712,623,267,582,-802,542,-667,64,-120,-298,512,564,360,-450,-356,96,758,-111,348,120}

    {624,-612,55,-45,-223,150,227,-505,752,679,288,-448,408,-270,700,-230,-757,2,274,388,-777,195,282,-777,-327,35,-153,247,826,-609}

    Returns: 4060

  14. {-1,1,-1,1,0,1,0}

    {0,-1,-1,0,1,1,0}

    Returns: 6

  15. {29,-41,-7,81,-11,39,27,24,25,34,34,79,3,62,88,-52,-21,-45,16,-42,-38,-13,-16,82,-92,-53,-58,-2,-64,-2}

    {3,-19,-90,91,-3,-48,-37,-94,-54,80,-20,22,51,69,26,-79,22,74,83,38,-77,15,12,-89,-31,91,-62,-12,-36,71}

    Returns: 4059

  16. {0,1,3,6,10,15,21,29,38,48,59,72,86,102,119,137,156,176,197,219,242,266,291,317,344,372,401,431,462,494,527,561,596,632,669,707,746,786,827,869,912,956,1001,1047,1094,1142,1191,1241,1293,1346}

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}

    Returns: 19600

  17. {-3,-3,-3,-3,-3,-3,-3,-2,-2,-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3}

    {2,-3,1,0,-2,3,-1,2,-3,1,0,-2,3,-1,2,-3,1,0,-2,3,-1,2,-3,1,0,-2,3,-1,2,-3,1,0,-2,3,-1,2,-3,1,0,-2,3,-1,2,-3,1,0,-2,3,-1}

    Returns: 229

  18. {4180,-6561,-6599,5049,8375,-3275,-9637,2584,3714,2207,-8162,-9574,5432,-2209,-199,-476,6308,-2978,277,6532,840,-5015,5676,6569,-5440,4517,-4103,5919,-2757,-7961,4472,-9077,53,4232,8713,-4776,-3609,-9466,-580,452,9204,-6837,-3935,-5012,1804,-3525,1129,2432,2975,552}

    {2922,7410,-5862,1535,-4795,8864,2075,-922,-2860,-8416,-7789,520,3910,-8056,1505,3967,4896,1073,6976,5043,-6679,-2960,-9542,-9075,-1609,9201,-4658,-7793,5430,3687,-4186,-8351,-8501,4718,-2654,-1531,-5214,577,6923,-4310,-264,1949,-2277,8904,-1153,-8013,7140,6530,-4958,1547}

    Returns: 19600

  19. {-7,4,-3,-12,-17,-7,5,9,-7,-18,-18,2,20,7,-17,-11,-16,15,-17,3,-9,-18,-11,-16,-13,8,-1,11,-4,-13,8,-18,-12,14,16,17,-4,-8,-18,9,8,-19,18,-7,9,-9,1,2,-17,-5}

    {7,-20,1,-17,-6,-17,-15,-14,-20,19,-9,-7,-13,1,-20,-16,-20,-18,-2,-2,14,-15,-12,-6,-6,-2,-10,-2,-12,18,-13,-2,13,-15,11,-14,1,16,3,-12,0,18,8,20,4,0,-10,-15,-10,-10}

    Returns: 15602

  20. {-36,-25,0,-8,-24,-29,-16,17,20,-32,38,-30,9,-18,24,-22,33,22,-39,19,14,29,13,-3,19,2,30,-40,20,-13,-8,-14,-28,-27,1,-6,-31,10,11,-4,10,25,-38,23,-5,26,19,-21,-1,-11}

    {19,3,-10,-29,-34,-9,-37,-33,22,-25,-32,39,10,-40,-14,39,2,15,-38,4,-39,38,-31,-21,28,4,-13,-37,9,-30,38,-16,-25,-40,-35,-9,-15,16,-31,1,26,20,-37,36,1,-26,-27,2,-25,6}

    Returns: 19201

  21. {-77,60,30,-21,-28,-44,-5,-54,-10,28,61,67,24,-4,30,-44,-3,-31,-47,19,-4,-23,-40,31,-76,40,-68,9,8,-4,-38,-66,-55,-69,-6,-52,52,18,52,13,35,-72,79,-67,71,-63,-1,17,-53,61}

    {59,-76,14,65,-43,72,-21,-61,60,-46,79,-48,-13,-55,-60,-38,72,43,-36,-37,46,-55,49,-22,46,25,-17,73,66,-41,-19,-48,71,-17,-9,39,43,-24,-16,-23,-75,-75,-2,-42,-67,-10,-22,-52,39,-23}

    Returns: 19532

  22. {85,-41,-90,-115,98,16,37,-119,-75,68,52,29,-94,-112,-54,64,110,-51,79,57,92,-87,-81,118,-71,-28,78,113,-9,-44,59,112,-90,110,62,66,75,-16,-53,-111,-41,-89,6,-88,-39,-97,-15,-96,57,-9}

    {-9,9,-106,-69,-91,47,66,-73,78,-85,85,-77,-102,20,30,-24,83,30,28,-42,36,-92,-9,-98,-66,51,24,83,108,-41,85,-56,12,-55,53,111,17,62,40,-70,116,55,-94,-52,106,-59,97,-80,77,12}

    Returns: 19582

  23. {188,-86,28,-69,-144,198,15,106,-184,137,-36,-159,-196,81,179,-51,-122,75,-40,-101,-60,30,129,-120,-30,184,104,-68,88,174,-179,-172,-13,-97,161,6,-15,179,15,83,-149,-141,142,59,-51,184,-19,52,-20,9}

    {147,-144,-167,-183,-200,-67,-68,14,-162,-74,-83,-188,174,-169,93,4,-1,78,-129,-42,68,76,175,128,-43,135,150,-17,144,172,-37,-166,131,81,103,124,-155,158,133,-37,-149,-30,195,116,57,47,-44,-199,-122,189}

    Returns: 19594

  24. {-2222,-795,4241}

    {-6830,-53,2269}

    Returns: 1

  25. {0,1000,10000}

    {0,-1000,-10000}

    Returns: 0

  26. {-20,11,-14,13,5,10,9,-4,-9,8,-19,18,6,5,-4,-6,-19,-15,-2,18,12,-13,-17,10,2,9,12,-18,13,0,7,-14,-14,12,-12,-5,14,5,-14,14,-10,14,-5,15,-18,-10}

    {1,-2,-10,-10,-2,-4,10,-10,-14,16,-3,17,8,2,3,-19,5,-10,-19,3,-11,9,-19,1,-11,-20,1,-17,-14,-16,-13,-12,-5,3,-1,12,-17,-5,-15,-13,-10,10,0,15,-2,-14}

    Returns: 12647

  27. {-27,-26,2,5,15,20,25,-33,-18,-23,-8,-36,38,-32,-21,15,19,3,35,21,40,18,-20,26,32,-10,-6,35,-30,-1,-13,-23,-17,39,-27,-8,-21,21,10,-15,40,-2,40}

    {-36,33,-6,-40,-24,-35,-8,20,24,-4,39,12,-39,-4,8,17,-20,37,26,-27,14,26,-34,23,35,28,32,-11,33,23,-7,-37,28,18,35,-16,-3,21,-17,26,-10,-24,-11}

    Returns: 12181

  28. {17,-9,-42,9,16,-3,-8,-19,-8,-20,-31,43,24,-3,-9,24,29,22,-13,7,-45,-2,-39,41,4,31,41,-12,-8,-8,32,-3,-11,-28,-39,-5,-35,0,40,23,10,4}

    {25,41,-19,-15,36,-19,-17,-37,-24,-42,12,29,4,35,6,39,-37,-43,13,-18,36,-10,-12,28,-31,-32,6,23,-29,2,-30,-40,24,-27,13,-27,-15,-40,9,33,37,20}

    Returns: 11332

  29. {11,-26,-22,-2,47,-3,26,-10,-18,15,1,10,15,-18,-25,13,42,1,-37,-3,16,15,27,-30,-14,-37,-12,41,12,46,48,-47,-2,-3,-42,-14,5,9,30,24,0,-2,17,-11,27}

    {37,1,-18,13,-48,3,47,-6,-39,31,9,-19,17,31,-44,-3,21,34,-10,-46,-21,-24,0,16,17,34,24,-48,38,11,43,-23,-38,19,27,5,32,-42,-46,-6,39,-50,32,17,-48}

    Returns: 13994

  30. {-57,-56,99,-85,74,96,22,-80,47,46,95,66,48,39,-16,-79,-16,77,17,-28,59,30,-77,-49,-87,-92,33,14,39,-85,19,57,-1,-75,31,-65,76,11,-7,-5,8,36,-81,-14,52,20,40,-85}

    {-67,54,2,-54,52,-60,2,-9,-43,-93,-41,79,-3,-48,64,71,85,54,59,-33,-20,15,13,50,91,51,96,-34,-59,-44,-32,-54,-93,-17,-68,23,95,-5,-97,77,13,94,-38,61,77,-51,58,-45}

    Returns: 17268

  31. {-33,-21,69,70,-70,-53,75,-27,26,93,42,30,8,62,82,-69,92,-94,21,87,-39,24,-75,68,-52,-71,94,90,86,-55,50,29,-25,-48,-86,-23,67,14,-59,-8,-16,8,81,-22,67,-56,-35,44,-78}

    {81,29,-63,-31,-47,-64,-9,8,19,71,-22,-79,73,14,-22,16,-71,-44,73,6,-62,-75,-82,-72,-38,-89,-65,15,-16,40,84,52,70,37,36,-29,50,57,7,15,57,-78,58,-81,-37,-88,52,-4,-38}

    Returns: 18400

  32. {6417,-2652,8661,120,-2503,1161,8574,-4900,-5111,8946,-4216,4539,-3316,-9759,-6328,6190,-6851,3468,-5546,-9529,7582,556,4839,-3938,1053,-3324,1381,1992,-9948,343,5713,6793,6240,7643,827,-3668,5609,1858,-4680,4842,-2200,1693,-2164,-9862,-8254,6722,-811,7886,-7538,500}

    {3433,8188,-9097,-7057,1848,9937,3195,-1575,-8266,-26,-9799,7743,-2715,-2675,2554,5744,9935,6510,-1601,8184,495,8909,-6668,-895,-9235,-3373,4155,7557,-1658,1662,-1870,-8349,7984,-7552,8643,-3396,2714,314,1126,8648,2638,-1952,720,7479,-2228,-7362,3260,-8189,-3505,736}

    Returns: 19600

  33. {-6165,-4097,-850,-4299,-1058,7062,333,7669,9558,-9978,-4567,7388,6789,4852,-4826,-9383,-656,-6486,-5378,7221,6971,-4777,4712,9004,415,-726,5425,-458,8804,8682,-6698,2673,-8544,5559,1790,8311,-4042,-8587,8314,-8091,-7192,-3008,-9976,-9412,-6671,7501,2162,1068,4744,-2206}

    {6691,6606,4717,1721,-875,-2316,-8440,-8416,-4746,493,8090,6624,6617,-5211,6710,-3885,-4324,5825,5425,-472,-7699,-2649,-8949,-2035,4347,-9474,8958,5231,-3651,7413,8395,-7213,-6561,4029,5628,-9746,-6654,1573,-3444,2816,185,-4206,-4337,8971,-2934,-7995,-3818,1854,6730,9933}

    Returns: 19600

  34. {1253,-5542,-6639,-4998,-3334,9242,-7908,3957,4225,-8902,-1198,-9764,-6828,-538,-7046,-4955,5539,7283,-1490,3970,2638,-6389,8305,5666,-224,-1850,-6812,-2907,7555,-2981,892,-5168,-7048,-247,-967,289,6308,4689,1306,2699,-8463,-3989,-1508,-8962,-1367,4559,5135,-9471,-2975,-4911}

    {6227,5023,2251,-9502,-3598,1711,-73,1023,2494,-2708,5977,5505,-7772,8533,-9134,6487,5139,5140,8731,7151,7828,5794,8772,-6897,-5793,4425,-6241,2905,-5644,9443,-1341,-6077,-4825,-8112,6334,3905,7701,-889,-8014,-3016,1453,-2739,6885,-5817,80,7651,5384,-8105,685,-871}

    Returns: 19600

  35. {-3,1,-6,-1,-4,-2,1,2,-5,-5,6,-2,-6,-6,-2,5,-1,4,4,-3,6,-5,-5,1,0,0,5,3,0,-4,-4,-4,1,-4,-2,-4,-6,5,0,5,1,1,-3,5,6,-3,3,-4,1,-1}

    {4,-1,3,6,3,-3,2,4,-1,6,-4,6,-3,0,5,3,0,4,-5,-2,1,-5,-3,4,5,3,5,6,-5,-4,-2,2,5,4,3,-1,-4,-3,-1,-5,-4,1,-1,-1,-6,6,-1,6,-6,-1}

    Returns: 2606

  36. {2,-2,4,2,1,-3,1,-1,-1,4,-2,2,3,-1,-3,-3,-4,2,3,4,0,-2,2,-4,3,3,1,3,1,3,3,0,-2,-2,-2,0,-4,0,0,3,1,-2,-4,-3,0,4,0,3,4,-3}

    {0,0,-3,3,2,2,3,-1,-2,0,1,4,3,4,-4,4,2,-3,1,-4,3,-2,-4,-2,4,-3,-3,-4,1,2,0,0,2,-1,-3,-2,-4,-3,-4,-1,0,4,-3,-1,-1,-1,4,-2,4,0}

    Returns: 662

  37. { 41, 8467, 6334, 6500, 9169, 5724, 1478, 9358, 6962, 4464, 5705, 8145, 3281, 6827, 9961, 491, 2995, 1942, 4827, 5436, 2391, 4604, 3902, 153, 292, 2382, 7421, 8716, 9718, 9895, 5447, 1726, 4771, 1538, 1869, 9912, 5667, 6299, 7035, 9894, 8703, 3811, 1322, 333, 7673, 4664, 5141, 7711, 8253, 6868 }

    { 2929, 9880, 1020, 6793, 4467, 208, 152, 3139, 395, 8507, 7918, 2511, 9540, 1802, 9115, 2047, 5659, 1665, 7934, 3915, 7366, 9170, 197, 984, 6789, 2379, 1364, 1997, 4888, 5118, 4710, 9427, 9250, 899, 2630, 8603, 2284, 4297, 3152, 7172, 1629, 4114, 1396, 3741, 7017, 2752, 5307, 7096, 6311, 2474 }

    Returns: 19600

  38. { -10000, 0, 9999 }

    { 0, 1, 2 }

    Returns: 1

  39. { -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

  40. { 3922, 8571, 8612, 8403, 2394, 8441, 3781, 2001, 6068, 2152, 2814, 3078, 514, 985, 917, 5131, 2225, 5140, 7050, 2025, 9942, 4318, 9120, 7484, 5442, 9087, 7652, 6976, 1390, 5584, 1881, 1995, 6581, 9227, 6321, 7548, 6963, 4057, 344, 7236, 4203, 3103, 8098, 6762, 2223, 1711, 1135, 5902, 6156, 199 }

    { 9437, 6036, 9292, 1976, 2243, 8222, 6680, 5991, 2979, 4882, 3492, 40, 8576, 4699, 3658, 1921, 9427, 6540, 3279, 609, 2183, 948, 9572, 7529, 6499, 4573, 7405, 9586, 6022, 7498, 7247, 206, 6680, 4851, 3836, 4896, 6016, 5654, 3157, 3381, 5732, 3897, 6441, 1255, 5866, 9054, 3784, 250, 3123, 5858 }

    Returns: 19600

  41. { 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400, 1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400, 2500, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    { 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200, 1300, 1400, 1500, 1600, 1700, 1800, 1900, 2000, 2100, 2200, 2300, 2400, 2500 }

    Returns: 14376

  42. { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    { 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 150, 168, 190, 215, 245, 300, 400, 600, 900, 1300, 1700, 2400, 3200, 4100, 5100, 6300, 7600, 9000, -1234, -325, -42, -5134, -242, -642, -4132, -9999, 1425, 7534, 3142, -2514, 0, 123, 415 }

    Returns: 19581

  43. { -10000, 946, 7711 }

    { -10000, -3235, 946 }

    Returns: 1

  44. { -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, 1111, 2222, 3333, 4444, 5555, 6666, 7777, 8888, 9999, 654 }

    { 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, 1214, 2455, 5399, 1209, 4928, 287, 988, 129, 299, 1199 }

    Returns: 19592

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.
This problem was used for: