Danger! Earth has been invaded by aliens from Planet Vega!

Fortunately, earth still has a chance. There is a machine, called "The Pacifier" which when activated turns all the aliens into peaceful, gentle and friendly beings. But to activate it one has to pass several tests. You have passed all of them with success, but the last one, most critical, is left. Mission: calculate the area of the above knight tour, time: 30 seconds max.

"What to do! Mmm fast fast, remember some math courses you had back then. Let's see, yes I remember some obscure math teacher who taught some obscure theorem called Pick's theorem. Yes!!! Must use Pick's theorem. So let's see, ...".

And you saved earth (hopefully...) :-)

So, why such an intro? Well, in this short essay we will talk about how to calculate polygon areas like the one above in a very short time, which we hope you will enjoy.

First let us start with the basics.

How to calculate the area of a regular polygon? Well, if we draw an inscribed circle in it like for example, in the hexagon:

We see that the intersection of the circle and the polygon, when joined in the center, makes the altitude of six congruent triangles. This altitude is called the apothem. As the area of a triangle is simply a base times its altitude divided by 2, we have:

Area of a triangle = ½·s·.

As we have as many triangles as we have sides (n):

Area of a polygon = ½·s··n.

Can we simplify this further? Yes! It is not hard seeing that s and are related as follow:

s = 2··tan()

Thus we have:

Area of a polygon = ·n·tan()

Ok, we have seen regular polygons. But what about irregular ones, like the monster above? This is a little bit more complicated, and has been the subject of research. Let us start with a simple triangle:

Well, here are several way to calculate its area:

1. ½·b·h
2. ½·a·b·sin(C)
3. where = ½·(a+b+c)

We see that it is relatively easy to do. Does it help us to calculate the area of bigger polygons? Yes! of course, simply divide the polygon into triangles, and calculate the area of each:

What's more, there are many ways to make this division, thus one can choose one that is the easiest to calculate.

This is the initial idea that Problem Online used, and it is not a bad one given that the movement of the knight is fixed, thus similar triangles are bound to arise. That said, it is not always very clear how to cut the polygon, and it can generate mistakes.

Let us now see how to calculate areas of irregular polygons using a more algorithmic approach.

Given:

Let us calculate the area using an elegant trapezoid approach.

Let us divide the polygon into trapezoids by having always two consecutive vertices each joined perpendicularly to a base line, as bases, and the shortest distance between the bases as altitudes.

We can easily see that the area of the polygon is the sum of the areas of the trapezoids [a,f], [f,e] and [e,d] minus the sum of the areas of the trapezoids [a,b], [b,c] and [c,d].

The area of a trapezoid being the sum of the bases times the altitude divided by 2, an algorithm can relatively easily be made into a program. And this is the way the Area Calculator written by Miodrag Mladenovic actually works... :-) And it is elegantly implemented! I would encourage you to go and have a look.

There are other nice algorithms, but one of the nicest must be Pick's theorem. This one, although not that easy to program, can be used to find the area of the complicated polygon given at the beginning most easily, by hand!

The theorem works for simple lattice polygons, that is for polygons which do not self-intersect, and which have their vertices on a regularly paced square grid nodes.

The theorem states that the area of such a polygon is the sum of the lattice points on its boundary divided by 2, plus the sum of the lattice points in its interior, minus 1.

In other words, if I is the sum of the interior lattice points of the polygon P, B the sum of the points on its boundary, and A(P) its area, then:

A(P) = I + ½·B - 1

It is quite an incredibly elegant result, and very easy to use.

Let us apply it to the following polygon:

We find that B = 14 (a straight line can host more than 2 boundary points!), I = 22, thus A(P) = 22 + ½·14 - 1 = 28.

Let us apply it to our first example:

One thing we can note straightaway in our case, given the movement of knights, the sum of the points on the boundary of our polygon is simply the number of moves of the knight. So in our case, B = 18. For the interior points, we simply go line by line and we get I = 17, thus:

A(P) = 17 + ½·18 - 1 = 25

Yes, it takes even less than 30 seconds to find this! :-)

Itamar Faybish