Statistics

Problem Statement for "AlmostConvexPolygons"

Problem Statement

A polygon is a figure on a plane bounded by a closed polyline with no self-intersections. A diagonal is a line segment that connects two non-adjacent vertices and lies completely inside the polygon. Every diagonal divides the polygon into two other polygons.

A polygon is called convex if every line segment that connects two non-adjacent vertices is a diagonal. A polygon is called almost convex if it is convex or if there exists a diagonal that divides it into two convex polygons.

You are given a set of points. The coordinates of the i-th point are (x[i], y[i]). Return the number of distinct almost convex polygons whose vertices all belong to the given set.

Definition

Class:
AlmostConvexPolygons
Method:
count
Parameters:
int[], int[]
Returns:
int
Method signature:
int count(int[] x, int[] y)
(be sure your method is public)

Notes

  • The answer will always fit in 32-bit signed integer.

Constraints

  • x will contain between 3 and 15 elements, inclusive.
  • y will contain the same number of elements as x.
  • Each element of x and y will be between -100 and 100, inclusive.
  • No three points from the given set will lie on the same straight line.

Examples

  1. {-2,2,-2,2}

    {-2,-2,2,2}

    Returns: 5

    We can construct 4 triangles and 1 square. All these polygons are convex and therefore are almost convex.

  2. {-2,2,-2,2,3}

    {-2,-2,2,2,0}

    Returns: 16

    Point (3, 0) is added to example 0. Now we can construct 10 triangles, 5 quadrangles and 1 pentagon. All of them are still convex.

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

    {-2,-2,2,2,1}

    Returns: 22

    Point (0, 1) is added to example 0. We can construct 10 triangles, 9 quadrangles and 4 pentagons. All of them are almost convex except one pentagon (-2,-2) - (0,1) - (2,-2) - (2,2) - (-2,2) - (-2,-2).

  4. {0,5,0,2,1}

    {0,0,5,1,2}

    Returns: 26

    Here there are 10 triangles, 13 almost convex quadrangles and 3 almost convex pentagons: (0,0) - (2,1) - (5,0) - (0,5) - (1,2) - (0,0); (0,0) - (5,0) - (0,5) - (1,2) - (2,1) - (0,0); (0,0) - (1,2) - (2,1) - (5,0) - (0,5) - (0,0).

  5. {-74,-96,-7,89,94,27,87,96,28,-29,4,-56,91,-48,11}

    {20,98,89,-36,-88,51,-23,-81,16,-57,0,-7,-53,10,-25}

    Returns: 57508

  6. {-53,-1,-40,-99,22,98,70,61,52,-97,-11,-96,-98,-92,48}

    {83,-99,-91,13,-97,-1,69,-78,84,20,98,-26,-15,37,-87}

    Returns: 32647

    A convex polygon on 15 vertices. The worst possible working time for my solution.

  7. {-3,45,2,-51,12,-29,-31}

    {10,21,46,-36,-2,12,50}

    Returns: 172

  8. {-62,8,-68,83,-69,-15,41,-19,-19,-3,-6,-44,-20,31,84}

    {-55,64,1,2,17,-53,-84,-42,7,-64,30,-36,-5,27,-52}

    Returns: 71416

  9. {9,-35,18,53,-81,93,-28,-55,84,-67,-61,64,-47,81,34}

    {-62,31,41,81,-9,58,29,59,13,25,18,-9,-56,65,-39}

    Returns: 76791

  10. {-30,-29,-24,-21,-19,-11,-5,14,20,4,5,32,29,21,-19}

    {16,-9,-20,-26,-27,-28,-28,-26,-24,-10,-6,-9,3,21,24}

    Returns: 92199

  11. {-15,-14,-6,-1,1,9,11,2,14,14,12,9,3,-8,-14}

    {0,-5,-13,-14,-14,-11,-10,-3,-2,2,9,11,14,12,2}

    Returns: 86311

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

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

    Returns: 85951

  13. {-41,-24,-22,-12,0,26,39,-6,31,-4,1,25,-15,-21,-31}

    {-2,-31,-34,-40,-41,-34,-8,7,27,17,20,33,36,34,30}

    Returns: 91729

  14. {-48,-44,-39,-32,0,40,42,-21,35,-11,15,-9,-17,-30,-36}

    {7,-21,-29,-37,-48,-26,-22,1,32,21,45,47,45,37,32}

    Returns: 95532

  15. {92,31,77}

    {94,-84,39}

    Returns: 1

  16. {-5,-86,41,-21}

    {-38,33,80,30}

    Returns: 7

  17. {24,36,15,-51,83}

    {15,54,-95,-1,14}

    Returns: 22

  18. {3,-74,-35,-47,-2,99}

    {-16,-53,-87,33,81,3}

    Returns: 60

  19. {32,-80,18,43,-46,-35,-2}

    {-69,-69,16,16,86,45,-60}

    Returns: 172

  20. {75,-51,-18,12,-32,99,23,97}

    {66,1,-50,-14,-21,-65,2,-71}

    Returns: 402

  21. {60,69,-80,65,-49,-52,-87,48,-11}

    {29,-75,-83,25,-43,0,17,-8,23}

    Returns: 869

  22. {-82,-87,77,26,-8,-20,-27,80,-31,-8}

    {-29,93,76,-69,-61,67,-94,90,-7,-4}

    Returns: 2051

  23. {95,-32,0,-7,91,-60,-38,-74,-82,88,63}

    {-58,-95,-7,-67,-73,-5,-31,-61,44,-40,-11}

    Returns: 3847

  24. {-8,42,49,-12,-84,-98,62,93,-32,47,-36,18}

    {40,67,30,-30,94,1,34,44,-19,-4,38,-88}

    Returns: 7382

  25. {53,-100,-34,-82,72,57,5,62,2,69,68,42,3}

    {58,-61,21,-34,-76,69,-19,8,-29,54,14,57,-49}

    Returns: 15605

  26. {-8,28,-82,94,23,70,-63,-77,-46,36,-72,63,8,46}

    {-51,81,-8,81,-88,-67,68,-21,-22,8,-74,87,35,10}

    Returns: 28393

  27. {-15,-24,-51,97,-82,75,6,-48,-87,99,23,73,-75,61,-49}

    {55,57,-33,97,-78,71,9,-27,-6,-60,-45,33,-42,-95,27}

    Returns: 50403

  28. {-76,-76,-66}

    {84,91,76}

    Returns: 1

  29. {-42,-15,-69,-37}

    {-28,-35,-22,-34}

    Returns: 5

  30. {-2,-90,-10,-28,-39}

    {-56,-52,-57,-51,-48}

    Returns: 22

  31. {-24,-93,-64,-83,-39,-35}

    {24,25,7,9,-5,16}

    Returns: 66

  32. {5,51,10,34,37,27,44}

    {-55,-34,-36,-53,-38,-37,-53}

    Returns: 171

  33. {-39,-48,-68,-59,-44,-85,-55,-84}

    {-73,-74,-83,-74,-72,-75,-72,-71}

    Returns: 397

  34. {-1,-12,35,-6,72,52,0,63,69}

    {20,-24,-23,64,-14,65,39,44,60}

    Returns: 818

  35. {-48,-45,-74,-69,-53,-27,-61,-24,-92,-30}

    {4,-50,-43,-37,11,69,51,3,-50,-2}

    Returns: 2068

  36. {-59,-67,-67,-63,-64,-89,-89,-76,-65,-71,-79}

    {54,-15,61,58,-41,70,1,65,69,75,-33}

    Returns: 4106

  37. {0,-6,-4,-3,0,-2,2,-9,-13,6,-3,2}

    {-36,51,-44,10,-15,-41,-10,51,64,-28,59,61}

    Returns: 7580

  38. {10,-69,-67,20,-49,-91,55,20,67,5,-27,-46,-66}

    {-48,-40,-60,-37,-66,-58,-67,-52,-60,-51,-50,-62,-58}

    Returns: 14703

  39. {-27,-57,-34,-29,-16,-52,3,-51,-22,-44,-33,-33,-32,-2}

    {79,61,59,50,71,63,78,72,70,64,53,78,74,59}

    Returns: 27260

  40. {-28,-21,-61,-20,-50,-31,-55,-23,-47,-22,-24,-31,-34,-82,-54}

    {3,56,56,27,0,61,26,-6,-3,12,7,11,41,5,64}

    Returns: 61018

  41. {1,0,0}

    {-1,-1,0}

    Returns: 1

  42. {0,1,0,1}

    {0,0,1,1}

    Returns: 5

  43. {1,1,0,-1,-1}

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

    Returns: 16

  44. {2,-1,-1,1,2,1}

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

    Returns: 60

  45. {2,1,-1,-1,1,2,0}

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

    Returns: 141

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

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

    Returns: 426

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

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

    Returns: 824

  48. {-3,-4,3,-5,1,-2,7,4,7,6}

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

    Returns: 1845

  49. {-4,-1,-4,0,2,3,3,1,5,7,7}

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

    Returns: 3946

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

    {1,6,1,4,2,-5,5,6,7,2,-2,-1}

    Returns: 7908

  51. {-8,1,-5,-5,1,-4,4,5,5,2,0,-6,2}

    {4,-5,5,2,-7,7,1,7,-7,0,8,-1,-5}

    Returns: 14976

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

    {-5,-5,-1,-8,7,8,1,9,-1,0,7,-8,-2,0}

    Returns: 31869

  53. {7,2,-10,1,7,-1,12,1,-2,-6,-12,-10,-12,11,4}

    {-4,11,10,12,-1,-9,-4,11,-8,-11,0,2,9,-8,10}

    Returns: 61070

  54. {-87,-83,-86,-83,-71,-79,-76,-72,-65,-60,-68,-51,-66,-46,66}

    {10,-90,-14,-17,-85,-36,-53,-75,-59,-63,-41,-84,-42,-85,-83}

    Returns: 36971

  55. {-64,-52,-60,-57,-44,-56,-45,-30,-17,2,-26,-12,0,-21,64}

    {38,-63,7,-6,-37,17,-11,-42,-45,-62,-19,-36,-50,0,-50}

    Returns: 44731

  56. {-90,-66,-53,80,-14,90,76,-4,57,-34,-21,-40,44,53,74}

    {-66,-90,-71,-84,-71,-50,-49,-50,-4,-39,-29,-38,15,29,73}

    Returns: 40793

  57. {-83,-82,-77,-73,-73,-47,-14,92,-39,40,65,52,-11,-74,43}

    {-5,-25,-77,-93,-31,-68,-51,-59,-17,-36,6,21,17,0,82}

    Returns: 51069

  58. {-29,-15,-9,-3,-4,-4,-18,17,11,4,-3,-16,-17,-24,-28}

    {-7,-26,-26,-27,-20,-19,-7,4,5,17,18,6,8,23,17}

    Returns: 53455

  59. {-21,-19,-18,-13,-10,-4,-10,-8,-2,-18,0,7,8,10,20}

    {-5,-11,-13,-19,-21,-21,-14,-14,-18,-7,-17,-17,-10,-9,-6}

    Returns: 56673

  60. {-48,-47,-45,-41,-26,23,33,39,12,27,31,-44,1,2,32}

    {-39,-42,-45,-48,-48,-45,-42,-34,-32,-25,-10,-37,-9,-6,31}

    Returns: 62436

  61. {-85,-82,-75,-72,-9,18,67,-15,46,60,-31,42,25,-37,-83}

    {-81,-83,-85,-83,-31,-11,33,-23,37,54,-26,59,42,-16,-78}

    Returns: 67036

  62. {-67,-63,-31,-7,6,25,27,25,32,0,32,11,-30,-57,-66}

    {-65,-66,-63,-60,-56,-46,-44,-27,-23,-35,26,7,56,-15,35}

    Returns: 71701

  63. {-16,-15,-13,-10,-4,0,10,15,15,11,14,2,-1,-1,-10}

    {-7,-12,-13,-14,-15,-15,-11,-10,-6,-3,3,15,12,16,15}

    Returns: 69369

  64. {-83,-68,-46,-11,69,28,16,86,72,51,29,19,8,0,-41}

    {-58,-63,-69,-70,-58,-52,-48,31,53,69,76,77,75,67,17}

    Returns: 63277

  65. {-9,-8,-4,-2,5,7,8,9,9,8,1,-3,-5,-8,-9}

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

    Returns: 61777

  66. {-40,-37,-29,-28,-22,17,26,39,39,30,9,5,-12,-39,-40}

    {0,-16,-28,-29,-34,-37,-31,-12,10,27,40,40,39,12,9}

    Returns: 32647

  67. {-38,-35,-36,-34,-35,-37,-30,-24,-24,-17,-8,3,19,5,28}

    {17,-37,-8,-13,-4,11,-16,-23,-22,-27,-31,-31,-29,-15,-32}

    Returns: 55019

  68. {-48,35,23,33,17,-19,36,-2,-14,44,-28,-26,-26,-16,42}

    {-44,-47,-46,-43,-41,-41,-35,-39,-40,-31,-39,-36,-32,-17,48}

    Returns: 52504

  69. {-75,-56,-61,-64,-55,-58,-27,-41,-17,-33,-8,-9,-25,-11,11}

    {43,-44,-16,-3,-27,-13,-55,-19,-54,-11,-37,-31,-13,-27,-51}

    Returns: 56903

  70. {-70,-61,-69,-58,-56,-51,-48,-15,-20,21,6,17,30,13,-43}

    {-28,-61,-31,-53,-56,-54,-56,-65,-57,-69,-58,-60,-63,-50,-34}

    Returns: 66362

  71. {-91,-89,-86,-86,-74,-58,-57,-58,-50,23,46,-64,-37,28,89}

    {6,-21,-50,-34,-81,-76,-68,-57,-44,-70,-43,-3,-3,44,72}

    Returns: 65768

  72. {-55,-3,-26,-45,-37,-20,35,-12,52,16,52,53,43,3,-26}

    {-44,-55,-50,-46,-47,-49,-48,-45,-43,-36,-31,-21,-22,-29,-35}

    Returns: 67840

  73. {-37,-35,-33,-32,-27,-25,-20,-24,-16,-14,-13,-20,-16,-15,-18}

    {34,0,-8,-13,-30,-22,-32,-16,-33,-28,-24,-7,-6,-6,31}

    Returns: 75381

  74. {-57,-44,-51,-33,26,44,-9,52,18,46,41,35,6,-48,-13}

    {24,-56,17,-3,-50,-37,-1,23,29,33,41,46,53,30,54}

    Returns: 76870

  75. {-40,-22,-23,4,11,23,43,-21,37,-16,20,3,-21,-36,-39}

    {7,-37,-26,-47,-44,-34,-16,3,-6,8,43,42,40,29,24}

    Returns: 83981

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

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

    Returns: 90508

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

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

    Returns: 90174

  78. {-61,-57,23,60,61,15,47,34,0,-43,-32,-46,-53,-59,-61}

    {-3,-23,-57,-15,-6,-2,39,51,62,21,52,41,31,18,6}

    Returns: 91225

  79. {-75,-60,-56,-48,-45,-43,-37,-27,-13,-20,4,8,31,42,43}

    {46,-5,-16,-36,-41,-43,-47,-36,-57,-38,-60,-60,-52,-42,6}

    Returns: 93031

  80. {-16,-13,-9,-6,-2,2,6,-4,13,16,10,-1,-3,-13,-15}

    {2,-10,-14,-15,-16,-16,-15,-6,-10,-4,13,16,16,10,8}

    Returns: 88357

  81. {58,23,77,74,5,-62,-16,45,62,-54,77,38,64,64,-36}

    {-62,10,0,53,33,95,54,-25,-75,89,-2,-11,-83,-85,73}

    Returns: 148973

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: