Ninjutsu - Google Code Jam 2011

ninjutsu.cpp

// This is an attempted solution to the Ninjutsu pratice problem from the Google Code Jam, 2011
// http://code.google.com/codejam/contest/dashboard?c=801485#s=p4
// Programmer: Greg Mann
// Location: Berkeley, CA

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <conio.h>
#include <vector>
#include <cmath>
using namespace std;

double ropeLength;
bool currentIsZero, candidateIsZero, currentIsGreater, currentIsFurther, currentIsEqual;

struct Coord  // structure for an individual (x, y) coordinate, with slope and distance for use by the algorithm
{
    int x;
    int y;
    double slope;
    double distance;
};

void setDistance(Coord *current, Coord *swing) {
    (*current).distance = sqrt(pow((double((*current).x - (*swing).x)), 2.0) + pow(double((*current).y - (*swing).y), 2.0)); }

void setSlope(Coord *current, Coord *swing) {
    (*current).slope = double((*current).y - (*swing).y) / ((*current).x - (*swing).x); }

double calcAngle(Coord *target, Coord *swing) {
    return (atan((*target).slope) - atan((*swing).slope)); }

bool testCurrent(Coord *current, Coord *candidate, Coord *swing)
{
    double currentAngle = calcAngle(current, swing);
    double candidateAngle = calcAngle(candidate, swing);

    candidateIsZero = false;
    currentIsEqual = false;
    currentIsFurther = false;
    currentIsGreater = false;
    currentIsZero = false;

    if (currentAngle > -0.00000001 && currentAngle < 0.00000001) currentIsZero = true;
    if (candidateAngle > -0.00000001 && candidateAngle < 0.00000001) candidateIsZero = true;
    if ((currentAngle - candidateAngle) > 0.00000001) currentIsGreater = true;
    if (((*current).distance - (*candidate).distance) > 0.00000001) currentIsFurther = true;
    if ((candidateAngle - currentAngle) > -0.00000001 && (candidateAngle - currentAngle) < 0.00000001) currentIsEqual = true;

    if ((*current).distance < ropeLength && currentAngle > -0.00000001)
    {
        if (currentIsEqual && currentIsFurther) return true;
        else if (currentIsZero) return false;
        else if (!currentIsGreater) return true;
        else if (candidateIsZero) return true;
        else return false;
    }
    else {
        //cout << "   f" << endl;
        return false; }
}

int main(int argc, char **argv)
{
	string filename = "E-small-practice.in";
	vector<Coord> setOfPoints;  // this will be the set of points for a given trial
	int T;

	ifstream inFile;
	inFile.open(filename.c_str());

	inFile >> T;
	int numPoints, bends, finalBends;
    double initialLength;
	for (int i = 0; i < T; i++)  // loop through trials
	{
        setOfPoints.clear();
        finalBends = 0;
        inFile >> numPoints >> initialLength;

        for (int j = 0; j < numPoints; j++)  // populate vector of coordinates for this trial
        {
            Coord tempCoord;
            inFile >> tempCoord.x >> tempCoord.y;
            setOfPoints.insert(setOfPoints.end(), tempCoord);
        }

        while (initialLength > 0)
        {
            // declare values in preparation for first loop
            ropeLength = initialLength;
            bends = 0;
            Coord *candidate;
            Coord *swing = &setOfPoints.at(0);
            Coord *current;
            (*swing).slope = -1;
            bool foundOne;  // bool to indicate that rope found a pivot
            bool firstLoop = true;

            do
            {
                foundOne = false;
                for (int k = 0; k < numPoints; k++)  // test each point for next swing
                {
                    current = &setOfPoints.at(k);

                    if (swing != current)
                    {
                        setSlope(current, swing);
                        setDistance(current, swing);
                        if (firstLoop)
                        {
                            if ((*current).distance < ropeLength)
                            {
                                candidate = current;
                                foundOne = true;
                                firstLoop = false;
                            }
                            else continue;
                        }
                        else if (testCurrent(current, candidate, swing)) candidate = current;
                    }
                    else continue;
                }
                if (foundOne)
                {
                    ropeLength -= (*candidate).distance;
                    swing = candidate;
                    bends++;
                    firstLoop = true;
                }
            } while (foundOne);
            if (bends > finalBends) finalBends = bends;
            initialLength -= 0.001;
        }
        cout << "Case #" << (i + 1) << ": " << finalBends << endl;
	}

	getch();

	return 0;
}