home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / ~Solutions Submitted / Problem 03 - Guiness / Solution.cp < prev    next >
Encoding:
Text File  |  1998-06-19  |  3.4 KB  |  142 lines  |  [TEXT/CWIE]
  1. /*
  2. Problem 03 - Perimeter
  3.  
  4. You are in charge of protecting a set of defenseless homeowners from predators
  5. that roam the area by constructing a single fence of minimum length that
  6. encloses all of the homes.  
  7.  
  8. The prototype for your solution is as follows:
  9.  
  10. typedef struct Node {
  11.     long xCoord;
  12.     long yCoord;
  13. } Node;
  14.  
  15. void Perimiter(
  16.     long numHomes,
  17.     Node homesToEnclose[],
  18.     long *numNodesInPerimiter,
  19.     long nodesInPerimiter[]
  20. );
  21.  
  22. You are given a list homesToEnclose of numHomes homes to protect  (numbered 0
  23. to numHomes-1) by constructing a fence around the homes. You should return a
  24. list nodesInPerimiter of the numNodesInPerimiter homes to be connected by a
  25. fence.  The fence must enclose all of the homes using the minimum amount of
  26. fencing material.
  27. */
  28.  
  29. #include <MacTypes.h>
  30. #include <Math.h>
  31. #include "Solution.h"
  32.  
  33. // Fill in your solution and then submit this folder
  34.  
  35. // Team Name: Team Guiness
  36.  
  37. #define FLOAT float
  38. #define PI        3.1415926535
  39. //-----------------------------------------
  40. static FLOAT    FindRadian( FLOAT    dx, FLOAT dy, FLOAT *d )
  41. {
  42.     FLOAT result = 0;
  43.     
  44.     *d = dx*dx + dy*dy;
  45.     
  46.     if ( dx!=0 )
  47.         {
  48.         result = atanf( dy/dx );
  49.         if ( dx < 0  )
  50.             result = result+ PI;
  51.         if ( dx > 0 && dy < 0 )
  52.             result = result + 2 * PI;
  53.         }
  54.     else if ( dy > 0 )
  55.         result = PI/2;
  56.     else if ( dy < 0 ) 
  57.         result = 1.5 * PI;
  58.     else 
  59.         DebugStr("\pidentical nodes?");
  60. //    result = atan2f( dy, dx );
  61.     
  62.     return result;
  63. }
  64. //------------------------------------
  65. static void TestRadian( void )
  66. {
  67.     FLOAT    stuff[] = { 10, 0, 0, 
  68.                              10, 10, PI/4,
  69.                              0, 10, PI/2,
  70.                              -10, 10, .75 * PI,
  71.                              -10, 0, PI,
  72.                              -10, -10, 1.25 * PI,
  73.                              0, -10, 1.5 * PI,
  74.                              10, -10, 1.75 *PI };
  75.     short i;
  76.     FLOAT a,b, ignore;
  77.     
  78.     for (i=0;i<8;i++)
  79.         {
  80.         a =  FindRadian( stuff[i*3], stuff[i*3+1], &ignore);
  81.         b = stuff[i*3+2];
  82.         }
  83. }
  84.  
  85. //-----------------------------------------
  86. pascal void Perimeter(
  87.     UInt32 numHomes,
  88.     const Node homesToEnclose[],
  89.     UInt32 *numNodesInPerimeter,
  90.     UInt32 nodesInPerimeter[]
  91. ) 
  92. {    
  93.     Node            *minNode, *thisNode,*curNode, *startNode;
  94.     FLOAT        *angles = (FLOAT*) NewPtr(sizeof(*angles) * numHomes);
  95.     FLOAT        lowRadian,curMinRadian;
  96.     Boolean        done = false;
  97.     UInt32        i;
  98.     
  99.     TestRadian();
  100.     
  101.     *numNodesInPerimeter = 0;
  102.     if (!angles) goto BAIL;
  103.     
  104.     minNode = thisNode = (Node*) homesToEnclose;                                // find min home in y, then x (if match)
  105.     for (i=0;i<numHomes;i++,thisNode++)
  106.         if (thisNode->yCoord < minNode->yCoord ||
  107.             (thisNode->yCoord == minNode->yCoord && thisNode->xCoord < minNode->xCoord ))
  108.                 minNode = thisNode;
  109.         
  110.     curNode = startNode = minNode;
  111.     lowRadian = 0;
  112.     while (!done)
  113.     {
  114.         curMinRadian = 10.0;    // something greater than 2 Pi
  115.         for (i=0,thisNode = (Node*)homesToEnclose; i<numHomes;i++,thisNode++)    // find node with minimal radian greater than last
  116.             {
  117.             FLOAT        r;
  118.             FLOAT        minD = 100000000, thisD;
  119.             
  120.             if ( thisNode == curNode ) continue;        // ignore the starting point
  121.             r = FindRadian(     thisNode->xCoord - curNode->xCoord,
  122.                                     thisNode->yCoord - curNode->yCoord, &thisD );
  123.              if ( r >= lowRadian )
  124.                  if ( r < curMinRadian || (r==curMinRadian && thisD < minD ) )
  125.                      {
  126.                      minD = thisD;
  127.                      minNode = thisNode;
  128.                      curMinRadian = r;
  129.                      }
  130.              }
  131.         UInt32 nodeIndex =  minNode - (Node*)homesToEnclose;
  132.         nodesInPerimeter[(*numNodesInPerimeter)++] = nodeIndex;
  133.         curNode = minNode;
  134.         lowRadian = curMinRadian;        // save the last radian as the lower bounds for the next search
  135.         if ( curNode == startNode )
  136.              done=true;
  137.     }
  138.  
  139. BAIL:
  140.         ;
  141. }
  142.