Statistics

Problem Statement for "ConvexPoly"

Problem Statement

Given a rectangular grid of squares, how many different convex polygons can be drawn whose vertices are all points on the grid and whose sides are either horizontal, vertical or (45 degree) diagonal?

We define the width of the given rectangular grid to be the number of intersection points along one if its horizontals (including both the leftmost and rightmost points). Similarly the height of the grid is the number of intersection points along one of its verticals. We want to count the number of different "grid polygons" that could be formed. A grid polygon is a polygon with the following properties:

  1. 1) Each vertex is located at a grid intersection point
  2. 2) Each edge of the polygon is either vertical, horizontal, or at an angle of 45 degrees.
  3. 3) It is a proper polygon, with no edge touching or intersecting another edge (except that adjacent edges touch at their common vertex).
  4. 4) The polygon is convex: every straight line joining any two interior points of the polygon is entirely contained in the interior of the polygon.

Two grid polygons should be counted as different if their boundaries are not identical. If they are the same shape but in different locations they are different. But placing an extra vertex in the middle of an edge does not change the boundary so it does not create a new grid polygon.

Create a class ConvexPoly that contains a method count that is given two ints w, the grid width, and h, the grid height, and that returns the number of grid polygons that could be formed.

Definition

Class:
ConvexPoly
Method:
count
Parameters:
int, int
Returns:
long
Method signature:
long count(int w, int h)
(be sure your method is public)

Constraints

  • w will be between 2 and 100 inclusive
  • h will be between 2 and 100 inclusive

Examples

  1. 3

    2

    Returns: 19

    XXXXXXX XXXXXXX XXXXXXX XXXXXXX X X X X X X X X X X X X X X X X . XXXX . X . XXXXXXX XXXX . XXXX . XXXX . XXXX . X . . . X . X X X X X X XX XX XX X X XX X X X X . X . XXXX . X . . XXXX . XXXX . . XXXX . X . XXXX . XXXX . . XXXX X X X X X X X X X X X X X X X X X X X X XXXXXXX XXXXXXX . XXXX XXXXXXX XXXX . . XXXX . XXXX . XXXX . X . . . X X X X X X X XX XX XX X X XX X X X X . . X . XXXX . X . . XXXX . XXXX All 19 possible grid polygons are shown above, with the polygon sides shown with 'X' and unoccupied grid points with '.'

  2. 2

    2

    Returns: 5

  3. 10

    2

    Returns: 369

  4. 2

    10

    Returns: 369

  5. 37

    24

    Returns: 602297464

  6. 24

    37

    Returns: 602297464

  7. 100

    100

    Returns: 8658940474595

  8. 100

    99

    Returns: 8321848660545

  9. 2

    98

    Returns: 42389

  10. 75

    75

    Returns: 901463408966

  11. 74

    75

    Returns: 855086433439

  12. 98

    2

    Returns: 42389

  13. 77

    76

    Returns: 1052628997154

  14. 31

    4

    Returns: 83885

  15. 64

    64

    Returns: 260327246384

  16. 81

    81

    Returns: 1649354923140

  17. 100

    2

    Returns: 44154

  18. 100

    3

    Returns: 262465

  19. 13

    95

    Returns: 289917230

  20. 31

    63

    Returns: 9623498203

  21. 47

    17

    Returns: 225299508

  22. 10

    50

    Returns: 18342651

  23. 25

    76

    Returns: 5313190292

  24. 8

    64

    Returns: 10389208

  25. 99

    40

    Returns: 117997155138

  26. 95

    98

    Returns: 6526945784253

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: