UVa 216 - Getting in Line

UVa Problem

Solution:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <limits>

using namespace std;

struct Point
{
   int x, y;
};

struct Link
{
   Point start, end;
   double distance;
};

class NetworkSolver
{
public:
   NetworkSolver(const vector<Point>& nodes) :
      mNodes(nodes), mTotalLength(numeric_limits<int>::max()),
      mConfig(nodes.size() - 1)
   {
   }

   double getTotalLength()
   {
      return mTotalLength;
   }

   vector<Link> getConfig()
   {
      return mConfig;
   }

   void solve()
   {
      vector<Point> buffer(mNodes.size());
      vector<bool> bFree(mNodes.size(), true);
      doSolve(buffer, bFree, 0);
   }
private:
   void doSolve(vector<Point>& buffer, vector<bool>& bFree, int level)
   {
      if(level == mNodes.size())
      {
         double currDist = 0;

         for(int iNode = 0; iNode < level - 1; ++iNode)
         {
            currDist += (16 + sqrt( (buffer[iNode].x - buffer[iNode+1].x)
                  * (buffer[iNode].x - buffer[iNode+1].x)+
                  (buffer[iNode].y - buffer[iNode+1].y)
                                    * (buffer[iNode].y - buffer[iNode+1].y)));
         }

         if(currDist < mTotalLength)
         {
            mTotalLength = currDist;
            for(int iNode = 0; iNode < buffer.size() - 1; ++iNode)
            {
               mConfig[iNode].start = buffer[iNode];
               mConfig[iNode].end = buffer[iNode+1];
               // Euclidean Distance
               mConfig[iNode].distance =
                     (16 + sqrt( (buffer[iNode].x - buffer[iNode+1].x)
                           * (buffer[iNode].x - buffer[iNode+1].x)+
                             (buffer[iNode].y - buffer[iNode+1].y)
                           * (buffer[iNode].y - buffer[iNode+1].y)));
            }

         }
         return;
      }

      for(int i = 0; i < mNodes.size(); ++i)
      {
         if(bFree[i])
         {
            bFree[i] = false;
            int tmp = buffer.size();
            buffer[level] = mNodes[i];
            tmp = buffer.size();
            doSolve(buffer, bFree, level+1);
            bFree[i] = true;
         }
      }
   }

private:
   const vector<Point>& mNodes;
   vector<Link> mConfig;
   double mTotalLength;
};


int main(int argc, char *argv[])
{
   int iNetwork = 1;
   int numComputers;

   while( (cin >> numComputers) && numComputers)
   {
      vector<Point> nodes;

      for(int iNode = 0; iNode < numComputers; ++iNode)
      {
         Point currNode;
         cin >> currNode.x;
         cin >> currNode.y;
         nodes.push_back(currNode);
      }

      // Node and Distance of result configuration
      vector<Link> links;

      double totalLength;

      NetworkSolver solver(nodes);
      solver.solve();
      links = solver.getConfig();
      totalLength = solver.getTotalLength();


      printf("**********************************************************\n");
      printf("Network #%d\n", iNetwork);
      for(int iLink = 0; iLink < links.size(); ++iLink)
      {
         printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n",
               links[iLink].start.x,
               links[iLink].start.y,
               links[iLink].end.x,
               links[iLink].end.y,
               links[iLink].distance);
      }
      printf("Number of feet of cable required is %.2f.\n", totalLength);
      ++iNetwork;

   }

   return 0;
}