1. #1
    AceInfinity's Avatar
    Join Date
    Feb 2012

    CodeJam Qualification Round

    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.

    #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;
    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);
    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.
    Last edited by AceInfinity; 04-08-2018 at 02:03 AM.
    Automation Programmer
    Microsoft MVP [2012 - 2018]

    • Ad Bot



Similar Threads

  1. A big Texas howdy from Round Rock
    By EdTittel in forum Introductions - New Members
    Replies: 5
    Last Post: 12-03-2017, 06:29 AM
  2. KB2538243 Merry-GO-Round
    By RickZler in forum Windows Update
    Replies: 6
    Last Post: 08-28-2015, 04:28 PM
  3. [C++] Google CodeJam 2010 Round 1C - Problem A. Rope Intranet
    By AceInfinity in forum Programming
    Replies: 0
    Last Post: 03-23-2014, 11:11 PM
  4. [C++] CodeJam Problem - 2010 (Problem B. Reverse Words)
    By AceInfinity in forum Programming
    Replies: 0
    Last Post: 03-23-2014, 08:31 PM

Log in

Log in