| 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) Each vertex is located at a grid intersection point
-
2) Each edge of the polygon is either vertical, horizontal, or at an angle of 45 degrees.
-
3) It is a proper polygon, with no edge touching or intersecting another edge (except that
adjacent edges touch at their common vertex).
-
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.
|