TCO 2017, Round 1A, 1000-Pointer (PolygonRotation)

James S. Plank

Sun Apr 9 22:05:35 EDT 2017
This is a fun problem. To solve this in the given time period, you need to have your A game on, and probably to have written a line-intersection procedure already. I have one now...

Let me walk you through a solution, by way of examples. I have put these examples into main.cpp with the given numbers.

Example 4

Here we have just four points, none of which are negative:

(0,3), (4,3), (4,1), (0,1)

This makes the following rectangle:

I think it's pretty clear that when you rotate this around the Y axis, you have a cylinder with a height of two and a radius of four. Its volume will be π (4)2(2) = 100.53.

Example 5

Now only three points, none of which are negative:

(0,3), (4,3), (0,1)

This makes the following triangle:

When you rotate this about the Y axis, you get a cone with radius four and height two. I certainly didn't have the volume of a cone memorized, but google told me that it's π r2h/3. In this case: 33.51.

Example 6

Back to four points, but again, none of them are negative:

(0,3), (4,3), (2, 2), (0, 2)

This makes the following trapezoid:

When you rotate this about the Y axis, you get a chopped off cone. To calculate the volume, follow the dotted line to the Y axis. Now there are two cones -- one of height 1 and radius 2, and one of height 2 and radius 4. Subtract the smaller from the larger, and you get the volume of the chopped off cone: π 422/3 - π 221/3 = 33.51 - 4.19 = 29.32.

This is an important case, so let's consider it a little further. When you see a trapezoid, it will turn into a chopped-off cone. To calculate the volume, you'll need to take the two rightmost points, turn them into a line, and then find out where they cross the Y-axis. That will give you a Y value, which is either the bottom or the top of two cones, one of which is the superset of the other. Calculate the volume of these two cones and their difference is the volume of the chopped-off cone. The next example will give you a little more practice.

Example 7

Here's a final initial example.

(0,5), (1,4), (4,3), (4,2), (2,1), (0,1)

As you can see by the horizontal lines, you can break this up into a triangle, two trapezoids and a rectangle:

Let's calculate their volumes when you rotate them about the Y axis:

Their sum is 102.63.

Now is a good time for your to write some code: Given a collection of x/y points, where the Y points are ordered from top to bottom as in the program, and none of the x values are negative, calculate the volume when the given line is rotated about the y axis. You do this by chopping up the line into triangles, rectangles and trapezoids, and using the formulas above. You actually don't need separate code for cones and chopped-off cones -- you can simply consider a triangle to be a trapezoid whose top/bottom point is on the y axis.

This is one place where I used some code that calculated the intersection of two lines -- to find the point where the trapezoid's line intersects the Y axis, intersect the point with a vertical line. You may find it easier at this point, to simply calculate the point where the line crosses the y axis directly.

Example 8 - Adding some negative numbers

Now, let's try the following points:

(0,3), (1,3), (1,2), (1,1), (0,1), (-2,1), (0,3)

I'm going to color the negative line blue and the positive one red, and then I'm going to do the same thing, only I'm going to turn the negative numbers into positive numbers:

As you can see, turning the negative numbers into positive numbers is ok, since you are rotating everything about the y axis. This gives you two distinct regions:

Their sum is 10.47.

Example 9 - As complex as it's going to get

Finally, here is example 9, which is equal to example 2 from the from the Topcoder writeup, only I have transposed the points up by four, so that the graph is less messy. Here are the points:

(0,6), (3,4), (0,1), (-2,3), (-2,5)

And here is the graph, with the blue points negated:

This graph has two things that make it a little harder than example 8:

  1. There are blue points at y values where there are no red points (e.g. (-2,5)), and there are red points at y values where there are no blue points (e.g. (3,4)).
  2. There is a point where the red and blue lines cross, which is at a y value that is not in either the red or the blue lines.
To handle these issues, my code had the following structure:
I don't give you a solution for this one, because this may turn into an honors lab problem. The good thing is that you can use all of the examples above to help you write and debug your code incrementally.