The C++ Program: robot-challenge.cpp

  1 /*
  2  * robot-challenge.cpp
  3  *
  4  *  Created on: Oct 27, 2009
  5  *      Author: Brianna
  6  */
  7 
  8 #include <iostream>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <vector>
 12 #include <fstream>
 13 #include <cmath>
 14 #include <iomanip>
 15 using namespace std;
 16 
 17 #define MAX_SPACES 10000
 18 
 19 //int doint()
 20 int main()
 21 {
 22     ifstream infile("files/robotchallenge.in");
 23     ofstream outfile("files/robotchallenge.out");
 24     
 25     int (*totalPenalty)[MAX_SPACES] = new int[MAX_SPACES][MAX_SPACES];
 26     
 27     while (true)
 28     {
 29           int numSpaces = 0;
 30           infile >> numSpaces;
 31           if (numSpaces == 0)
 32           {
 33              delete totalPenalty;
 34              return 0;
 35           }
 36              
 37           vector<int> spaceX, spaceY, penalty;
 38           
 39           for (int i = 0; i < numSpaces; i++)
 40           {
 41               int x, y, p;
 42               infile >> x >> y >> p;
 43               spaceX.push_back(x);
 44               spaceY.push_back(y);
 45               penalty.push_back(p);
 46           }
 47           
 48           // push the end point onto the vector and increase numSpaces
 49           spaceX.push_back(100);
 50           spaceY.push_back(100);
 51           penalty.push_back(0);
 52           numSpaces++;
 53           
 54           cout << numSpaces << endl;
 55           
 56           // calculate the cumulative penalties
 57           for (int i = 0; i < numSpaces; i++)
 58           {
 59               totalPenalty[i][i] = penalty[i];
 60               for (int j = i+1; j < numSpaces; j++)
 61               {
 62                   totalPenalty[i][j] = totalPenalty[i][j-1] + penalty[j];
 63               }
 64           }
 65           
 66           cout << "got total penalty" << endl;
 67           
 68           double bestScore[MAX_SPACES];
 69           for (int i = 0; i < numSpaces; i++)
 70           {
 71               // start by assuming we're starting at (0, 0) and stopping here
 72               bestScore[i] = sqrt(spaceX[i] * spaceX[i] + spaceY[i] * spaceY[i]) + 1;
 73               
 74               // add penalty if applicable
 75               if (i > 0)
 76                  bestScore[i] += totalPenalty[0][i-1];
 77               
 78               for (int j = 0; j < i; j++)
 79               {
 80                   double score = bestScore[j] + 1 + sqrt(
 81                          (spaceX[i] - spaceX[j]) * (spaceX[i] - spaceX[j]) +
 82                          (spaceY[i] - spaceY[j]) * (spaceY[i] - spaceY[j]));
 83                   if (j != i-1)
 84                      score += totalPenalty[j+1][i-1];
 85                   if (score < bestScore[i])
 86                      bestScore[i] = score;
 87               }
 88           }
 89           
 90           
 91           outfile << setprecision(3) << fixed;
 92           outfile << bestScore[numSpaces-1] << endl;
 93           
 94           
 95           
 96     }
 97     
 98     
 99 }