Today we continue our discussion with another problem that appeared in Algorithmic Engagements.
Problem statement:

I own a parcel of a polygonal shape. It has 10 sides and its area equals 23 (that is, it con­tains 23 unit squares). The corners of the parcel are: B2, B5, E5, E4, F4, F8, I8, I3, C3, C2, see figure.

Can you draw a polygon with:

(a)    6 sides and area 6?

(b)   8 sides and area 8?

(c)    10 sides and area 10?

(d)   12 sides and area 12?

(e)   14 sides and area 14?

Or a polygon with 13 sides and area 13? All sides of the polygon must be contained in grid lines. Each two consecutive sides must be perpendicular.

Solution:

 The given answer to all the questions is yes and there are quite a few solutions possible for each.
There is no polygon with 13 sides and area 13. Given that every two consecutive sides are perpendicular, the alternate sides have to be either all horizontal or all vertical.
In order for the polygon to bound, we must have equal number of horizontal and equal number of vertical edges. A polygon cannot be formed on a grid with odd number of edges.

The optimal solution can be described in a top down recursive strategy as follows: 

DrawPolygon(W, I, j, numEdges, ishorizontal, startx, starty, totalEdges) 

If I == startx and j == starty  and numEdges == totalEdges

   Return true

if numEdges > totalEdges
   return false;
for delta = -1 and 1
if isHorizontal:

    if (DrawPolygon(W, I, j+delta, numEdges+1, false, startx, starty, totalEdges))
      return true
else
    if (DrawPolygon(W, I+delta, j, numEdges+1, true, startx, starty, totalEdges))
       return true
return false;
}


#codingexercise
Double
GetSumNthAlternatePower (Double [] A,Double  p)

{

If ( A== null) return 0;

Return A.GetSumNthAlternatePower(p);

}