Statistics

Problem Statement

You are given an int m. Consider a square in the plane such that the corners of the square have coordinates (0, 0), (m, 0), (m, m), and (0, m). All the lattice points on the boundary of this square are red. That is, the red points have coordinates (0, 0), (1, 0), ..., (m, 0), (m, 1), ..., (m, m), (m-1, m), ..., (0, m), (0, m-1), ..., and (0, 1).

Some other lattice points are black. Each black point lies strictly inside the square. You are given two int[]s: x and y. These describe the black points: For each i, there is a black point at (x[i], y[i]).



You want to draw a triangle such that:

1. all three of its vertices are red,
2. all black points lie inside or on the boundary of the triangle.

Return the number of ways to draw such a triangle.

Definition

Class:

EnclosingTriangle

Method:

getNumber

Parameters:

int, int[], int[]

Returns:

long

Method signature:

long getNumber(int m, int[] x, int[] y)

(be sure your method is public)

Constraints

• m will be between 2 and 58,585, inclusive.
• x and y will each contain between 1 and 20 elements, inclusive.
• x and y will contain the same number of elements.
• Each element of x and y will be between 1 and m-1, inclusive.
• All points described by x and y will be distinct.

Examples

1. 4

   { 1, 2, 3 }

   { 1, 3, 2 }

   Returns: 19

   The picture shows the 19 ways to draw a triangle.

2. 7

   { 1, 1, 6, 6 }

   { 1, 6, 1, 6 }

   Returns: 0

3. 4

   { 2 }

   { 2 }

   Returns: 224

4. 10

   { 2, 6, 7, 6 }

   { 7, 7, 9, 3 }

   Returns: 81

5. 15

   { 7, 6, 5, 4, 3 }

   { 1, 4, 7, 10, 13 }

   Returns: 283

6. 58585

   { 14662, 14661, 14648, 14647, 14659, 14658, 14654, 14664, 14651, 14656, 14652, 14657, 14655, 14646, 14650, 14649, 14660, 14665, 14653, 14663 }

   { 14902, 14871, 14650, 14647, 14815, 14790, 14710, 14970, 14671, 14746, 14682, 14767, 14727, 14646, 14662, 14655, 14842, 15007, 14695, 14935 }

   Returns: 386135589376215

7. 58585

   { 14665, 14653, 14651, 14659, 14658, 14652, 14650, 14647, 14648, 14661, 14660, 14655, 14663, 14649, 14657, 14662, 14656, 14646, 14664, 14654 }

   { 29653, 29341, 29317, 29461, 29436, 29328, 29308, 29293, 29296, 29517, 29488, 29373, 29581, 29301, 29413, 29548, 29392, 29292, 29616, 29356 }

   Returns: 458097062494311

8. 58585

   { 29293, 29294, 29296, 29304, 29311, 29295, 29305, 29299, 29307, 29308, 29292, 29306, 29300, 29310, 29298, 29302, 29303, 29309, 29301, 29297 }

   { 14647, 14650, 14662, 14790, 15007, 14655, 14815, 14695, 14871, 14902, 14646, 14842, 14710, 14970, 14682, 14746, 14767, 14935, 14727, 14671 }

   Returns: 459641616278430

9. 58585

   { 29308, 29309, 29298, 29299, 29311, 29301, 29293, 29297, 29310, 29302, 29307, 29300, 29292, 29305, 29306, 29304, 29296, 29295, 29303, 29294 }

   { 29548, 29581, 29328, 29341, 29653, 29373, 29293, 29317, 29616, 29392, 29517, 29356, 29292, 29461, 29488, 29436, 29308, 29301, 29413, 29296 }

   Returns: 528775575069858

10. 2

    { 1 }

    { 1 }

    Returns: 32

11. 3

    { 1 }

    { 1 }

    Returns: 82

12. 3

    { 1, 2 }

    { 1, 1 }

    Returns: 42

13. 3

    { 1, 2 }

    { 1, 2 }

    Returns: 36

14. 3

    { 1, 2, 2 }

    { 1, 1, 2 }

    Returns: 21

15. 3

    { 1, 2, 2, 1 }

    { 1, 1, 2, 2 }

    Returns: 12

16. 58585

    { 58584 }

    { 58584 }

    Returns: 34322022242

17. 58585

    { 58584 }

    { 29292 }

    Returns: 150929112133973

18. 58585

    { 29292 }

    { 29292 }

    Returns: 536201513250114

19. 12605

    { 8930, 8727, 8377, 8797, 8645, 8761, 9103, 8795, 8832, 8875, 8516, 8684, 8629, 8105, 8948, 9504, 9167, 8688, 8837, 9099 }

    { 7732, 7638, 7167, 8240, 7765, 7692, 8062, 7601, 8081, 7896, 8110, 7459, 7111, 7700, 7692, 7834, 7815, 8217, 7809, 8129 }

    Returns: 3188803858638

20. 34825

    { 436, 1460, 870, 1388, 531, 1564, 2457, 493, 1091, 2971, 1041 }

    { 6828, 8916, 7391, 7814, 8060, 6484, 7155, 7816, 6839, 7021, 7748 }

    Returns: 15940360087743

21. 58585

    { 49163, 49043, 50478, 49227, 51944, 50199, 50026, 50697, 49339, 47295, 50016, 50098, 49947, 49894, 50013, 50051, 47485, 50934, 52864, 48758 }

    { 54755, 56437, 58494, 57790, 56032, 58446, 55581, 58380, 55586, 56861, 58435, 58086, 58505, 57643, 57531, 58215, 57858, 57790, 58428, 57894 }

    Returns: 35302342468574

22. 11529

    { 4275, 3711, 4225, 4289, 4563, 4138, 4186, 4263, 4088, 4755, 3998, 3981, 4184, 3509, 4045 }

    { 7868, 8331, 8081, 8038, 8342, 7916, 7954, 8446, 8205, 8331, 8517, 7803, 7958, 8089, 7553 }

    Returns: 2394791631671

23. 58585

    { 23955, 17551, 15878, 18311, 23568, 20216, 20563, 16006, 25487, 18250, 16701, 22785, 22136, 18581, 17374, 24744, 26933, 22557, 21288, 18380 }

    { 41768, 40104, 41612, 35141, 35186, 38879, 39538, 40000, 39855, 43826, 42080, 39327, 43226, 40852, 41515, 40217, 42204, 46420, 40203, 40877 }

    Returns: 187891309155729

24. 58585

    { 32102, 27183, 29486, 34993, 27363, 29075, 29466, 32933, 36143, 26510, 32825 }

    { 9582, 13282, 7557, 11057, 14606, 15286, 5868, 3916, 14260, 7996, 12365 }

    Returns: 117078456475156

25. 58585

    { 29038, 21523, 23067, 31010, 20429, 29704, 29749, 24135, 22992, 26014, 21653, 24663, 26478, 29880, 27340, 26850, 25512, 24460, 32479, 23144 }

    { 26895, 24593, 23647, 29928, 28702, 26201, 31505, 22726, 21644, 28214, 25686, 31862, 28039, 30289, 26783, 31065, 22266, 31001, 26952, 24053 }

    Returns: 242795141831282

26. 58585

    { 31656, 32534, 27018, 35863, 30681, 28776, 23785, 29303, 34612, 33505, 26962, 30300, 35817, 28528, 30478, 28460, 26807, 27646, 32799, 28172 }

    { 24621, 21246, 27884, 25449, 21642, 18730, 24800, 22963, 25972, 26244, 25916, 21932, 24108, 21616, 28007, 26658, 19676, 18397, 26052, 26055 }

    Returns: 250007195387594

27. 42645

    { 8109, 26779, 7406, 27288, 26800, 26741, 27814, 27593, 26546, 7561, 9969, 28562 }

    { 12197, 23632, 11814, 22839, 23547, 23771, 23770, 23902, 24095, 10256, 9581, 23360 }

    Returns: 26537613944743

28. 50069

    { 3227, 43560, 2637, 1276, 2729, 1969, 45493, 3312, 4461, 42119, 45328, 4022, 3875, 4924, 43973, 2447, 3675 }

    { 2273, 19654, 2556, 1617, 1985, 2096, 18762, 5360, 3086, 19282, 19051, 1651, 2490, 963, 18307, 1953, 2186 }

    Returns: 84783180

29. 58585

    { 17517, 16755, 4696, 5195, 15981, 3086, 3396, 2358, 1672, 16724, 14687, 1950, 15471, 4017, 17348, 1735, 3532, 1342 }

    { 34937, 31426, 12577, 10089, 34939, 10320, 7948, 10310, 12179, 34930, 34614, 13395, 35798, 10281, 34884, 10603, 9553, 11026 }

    Returns: 23712429778165

30. 58585

    { 31773, 4512, 31176, 5615, 30239, 30888, 33601, 5382, 31045, 33100, 31676, 3566, 34919, 31336, 30001, 4618, 2535, 31123, 31604, 31201 }

    { 50011, 56811, 50358, 54712, 47949, 48754, 52227, 54942, 50060, 52750, 51964, 56364, 51356, 50620, 51798, 55945, 54765, 48413, 51207, 47503 }

    Returns: 8867117842918

31. 58585

    { 4925, 9461, 9981, 9692, 9703, 19320, 9384, 10096, 16114, 18549, 10556, 8106, 12188, 11287, 7713, 5196, 16370, 11110, 13945, 13391 }

    { 10921, 2044, 38589, 40523, 7848, 34922, 7677, 6678, 9591, 41619, 32101, 8169, 12396, 7673, 13799, 10003, 36366, 9192, 37593, 10359 }

    Returns: 2551586131740

32. 32962

    { 3001, 6067, 2034, 4943, 1884, 1434, 7892, 6171, 2474, 5351, 5442, 7510 }

    { 16251, 22571, 16943, 22876, 14307, 14890, 22122, 25195, 11097, 13786, 23632, 22918 }

    Returns: 8356554423751

33. 54416

    { 17122, 19446, 49100, 16313, 52414, 11704, 21897, 45706, 52431, 47878, 49874, 18165, 17626, 50146, 14295, 16612, 20559 }

    { 22492, 22626, 27298, 13307, 21902, 22269, 23816, 23888, 18872, 20033, 19893, 17802, 18048, 20107, 15737, 23880, 18562 }

    Returns: 867125548096

34. 54728

    { 15941, 17644, 19649, 38092, 21097, 17936, 37859, 16284, 39738, 42455, 24019, 20055, 42739, 21148, 13303, 17756, 18854, 16095, 43133, 16985 }

    { 15036, 17636, 14402, 6216, 19259, 14953, 699, 17616, 3666, 10151, 19122, 17548, 2777, 12244, 13568, 17157, 10420, 16176, 4072, 13266 }

    Returns: 5600259725660

35. 16245

    { 4433, 4265, 3587, 2015, 1448, 1744, 3496, 4710, 4333, 3307, 4220 }

    { 12514, 5369, 4369, 4881, 5626, 5010, 5342, 12386, 12637, 4623, 12626 }

    Returns: 831978987247

36. 58585

    { 56004, 36216, 54121, 57433, 13253, 54387, 7890, 10208, 33966, 32559, 11382, 37093, 52727, 34690, 33425, 36960, 34355, 54825, 35943, 10777 }

    { 48233, 32200, 45659, 46488, 39182, 47054, 40447, 39427, 33507, 32471, 40562, 31465, 49392, 31765, 33132, 29664, 33795, 46980, 33248, 40724 }

    Returns: 2279686430468

37. 23033

    { 1143, 2858, 1976, 14003, 22310, 12947, 23000, 489, 13427, 2122, 1729, 1611, 13956, 1537, 22832, 2272, 13892, 605, 990 }

    { 6559, 7176, 6872, 767, 7594, 1790, 7778, 6290, 1391, 6669, 6482, 6713, 1795, 6605, 7427, 5434, 2145, 5956, 6034 }

    Returns: 0

38. 58585

    { 19715, 55225, 16649, 57942, 22440, 22888, 18264, 18827 }

    { 2116, 44947, 1623, 46520, 51638, 53005, 5656, 2858 }

    Returns: 0

39. 18249

    { 583, 11652, 439, 16677, 17981, 16864, 627, 17413, 11992, 2240, 268, 17378, 10413, 10330, 11479 }

    { 15429, 17665, 14697, 11172, 12942, 13929, 16818, 13141, 17631, 14175, 14574, 12804, 17833, 17454, 17865 }

    Returns: 0

40. 25214

    { 13568, 2665, 15448, 2171, 858, 17104 }

    { 5099, 7214, 5862, 7024, 7827, 2724 }

    Returns: 1153312789447

41. 58585

    { 14395, 26227, 23301, 23123, 16497, 20061, 31576, 21583, 29978, 19641, 25448, 24652 }

    { 21434, 19099, 2314, 5733, 20395, 20925, 5718, 2975, 8762, 18038, 6097, 3978 }

    Returns: 37306597904996

42. 58585

    { 36216, 19191, 24703, 19972, 37629, 37927, 21618, 38382, 29677, 30237, 30550, 39289, 26809, 36045, 36805, 37003, 28560, 36738, 38536, 30924 }

    { 17990, 57875, 46759, 53151, 21204, 16557, 53818, 16739, 23922, 19292, 17483, 25147, 53036, 24522, 16848, 21535, 16794, 19629, 21997, 19217 }

    Returns: 1791873870383

43. 58585

    { 52555, 35463, 35407, 31679, 57571, 53960, 10028, 31373, 13359, 52927 }

    { 16988, 54058, 52917, 50400, 44527, 19015, 7601, 50901, 4063, 44517 }

    Returns: 0

44. 22103

    { 18001, 8592, 8792, 17473, 6266, 6332, 7590, 8918, 8856, 7658, 9896, 8785, 18716, 8395, 8899, 16614, 7763, 9310, 9880 }

    { 16311, 12055, 13493, 16622, 12301, 11091, 13583, 18221, 18464, 12941, 18367, 17366, 16229, 17201, 18270, 15598, 18253, 18307, 17813 }

    Returns: 1117989587192

45. 7412

    { 2963, 5066, 5874, 6035, 5007, 5897 }

    { 2221, 4856, 4765, 4543, 5618, 4295 }

    Returns: 112918464728

46. 28801

    { 22792, 10794, 1445, 11354, 23011, 9845, 747, 952, 23238, 9600, 11840, 10219 }

    { 11043, 23411, 14605, 22245, 11616, 21795, 13721, 15363, 12437, 22440, 21018, 20905 }

    Returns: 18433840548

47. 45445

    { 23549, 33824, 5076, 39158, 27880, 39886, 30827, 44443, 22245, 26785, 40428, 43635, 814, 33151, 489, 1613, 24354, 20335, 22522, 21694 }

    { 36665, 36803, 42601, 10290, 36845, 9179, 36650, 12606, 32024, 39704, 8606, 8868, 42878, 37720, 43111, 42768, 38507, 41762, 36177, 40208 }

    Returns: 24223929599

48. 19100

    { 17996, 14099, 15029, 13866, 16992, 14333, 14377, 15411, 9861, 16956, 11128, 10715, 11495, 16096, 12378, 16045, 12805, 10315, 18412, 18678 }

    { 14043, 13584, 14873, 13297, 15509, 13265, 12583, 13701, 8405, 13609, 6373, 7660, 10286, 12489, 11703, 13798, 9999, 8374, 14958, 14472 }

    Returns: 349834346421

49. 48313

    { 46103, 43273, 15069, 12811, 26004, 14217 }

    { 6701, 8041, 12182, 13856, 19244, 15437 }

    Returns: 8425790381025

50. 15408

    { 5098, 5865, 4522, 7823, 13446, 10306, 5613, 4777, 4027, 8049, 4976, 5547, 4051, 4955, 13880, 6473, 5397, 9937, 13781, 9461 }

    { 10863, 11032, 3204, 12840, 89, 13438, 2860, 1848, 1272, 12560, 11041, 2859, 3179, 4717, 1502, 2750, 3836, 11828, 66, 12964 }

    Returns: 0

51. 14043

    { 9193, 13946, 11169, 8295, 6646, 7871 }

    { 13973, 10543, 6982, 3491, 4681, 9362 }

    Returns: 1

52. 14043

    { 74, 9102, 9333, 13886, 13590, 453 }

    { 3834, 13960, 13626, 1533, 1201, 3666 }

    Returns: 1

53. 14043

    { 10200, 68, 47, 7050, 7104, 10261 }

    { 9, 1350, 1443, 13959, 14012, 31 }

    Returns: 1

54. 4

    {2 }

    {2 }

    Returns: 224

55. 58585

    {25000 }

    {25000 }

    Returns: 524511855308808

56. 58585

    {29292, 29292, 29293, 29293 }

    {29292, 29293, 29292, 29293 }

    Returns: 536160327760764