CodeJam Qualification Round

[AceInfinity]

So it just finished and I attempted late last night and continued late today. I wish I would have spent more time on the questions. I had the first 2 down and the cubic one I was close to solving but I spent too much time doing research because my simple polygon function wasn't proper lol... Simplest mistake caught me - I would've had it if I spotted the real problem earlier. Anyways, my approach was to avoid having 2 axis rotation calculations knowing that if I rotated counter-clockwise or clockwise along the vertical axis by 45 degrees, it would remain at a surface area of 1km ^ 2. Rotating the cube from there along an axis perpendicular to the ground plane from that point by 45 degrees would allow the shadow to reach a max surface area. Looking at the 2D orthogonal projection from the 3D shape from the suns perspective would be the difference between a square and a perfect hexagon between the minimum and maximum shadow surface area. I decided to use 6 points for this reason, knowing that from the starting position 2 of the coordinates would be duplicated when the projection is a perfect square. I got this far, and I was considering bruteforcing the calculations comparing the shadow's surface area with the expected result. The only thing I didn't implement was the binary search calculation to do this, but I had written the matrix rotation from the base matrix of 0.5 across the diagonal. Anyways here's the corrected polygon area calculation function that messed me up.

[NO-PARSE]#define ABS(x) ((x) < 1 ? (x) * -1 : (x))

struct coord { double x, y; };

double polygon_surface_area(struct coord *pts, int count)
{
    int i;
    double x = 0.;
    for (i = 0; i < count - 1; i++)
    {
        x += (pts[i].x * pts[i + 1].y)
           - (pts[i].y * pts[i + 1].x);
    }
    x += (pts[i].x * pts[0].y) - (pts[i].y * pts[0].x);
    return ABS(x) * 0.5;
}[/NO-PARSE]

[NO-PARSE]struct coord coords[6];
coords[0].x = -.5; coords[0].y = .5;
coords[1].x = -.5; coords[1].y = .5;
coords[2].x = -.5; coords[2].y = -.5;
coords[3].x = .5; coords[3].y = -.5;
coords[4].x = .5; coords[4].y = -.5;
coords[5].x = .5; coords[5].y = .5;

double d = polygon_surface_area(coords, 6);
printf("%lf\n", d);[/NO-PARSE]

Result: 1.00000

To visualize my explanation above, the more you rotate the shape from the 2 opposing vertices, the more hexagonal the shape becomes if you picture the 2D projection from the 3D shape (orthogonal).

With the algorithm above, you just need the transformed matrix from the rotation matrix for the new cube vertex coordinates, and you're only concerned with these fixed 6 vertices out of the 8.