Judging the Southeast Region

An All Math All the Time problem. But, there are ways to solve it with only minimal math knowledge.

There is one bit of a sticking point, that caught some teams. The problem asks you to sort the answers by area, and by perimeter if the areas are equal – which means you have to compare real numbers. Comparing real numbers for equality in a program in problematic, because of roundoff error. You always need a tolerance. So, in Levees, what should the tolerance be? The problem tells you:

If two Quadrants have the same area when rounded to 3 decimal places, output the one with the largest perimeter first.

Some teams got caught by this, put answers in the wrong order when the areas were too close. In the judges’ programs, you’ll see that often, the judges converted the reals numbers to strings and then sorted the strings to get around this problem.

So, here’s the Judge Input, the Judge Output, the main solving program, a C++ program, and another C++ program.

Some solution ideas are inside the spoiler.
[spoiler]
First, you’ve got to find that middle point – the intersection of the two diagonals. Note that since the polygon is guaranteed to be convex, the diagonals are guaranteed to intersect at a single point inside the figure. Convenient! The main judge program uses Cramer’s Rule. There are other ways.

Once you’ve got that point, the perimeters are easy – just use the distance formula for each leg of each triangle. You can use your favorite technique to get the areas of the triangles – Heron’s formula, one half the cross-product of any two side vectors which share an endpoint, the programmer’s standard polygon area trick, you name it.

Then it’s just a matter of sorting the results, with the caveat described above.
[/spoiler]